十种常见经典排序
- 比较排序： 通过比较来决定元素间的相互顺序
- 非比较排序：
（冒泡排序，快排，插入，选择，基数，桶，希尔，归并，堆）
冒泡排序
算法思想
相邻元素两两比较，将较大（较小）的交换到后面。
代码
1 | public int[] bubbleSort(int[] arr){ |
复杂度分析
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
是否稳定
稳定
选择排序
1. 算法思想
将整个数组分为两部分：有序的和无序的，每次从无序的那一部分中选择最小（最大）的追加在有序部分的末尾。
2. 代码
1 | public int[] selectionSort(int[] arr){ |
3. 复杂度分析
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
4. 是否稳定
选择排序涉及到当前位置元素和后半段最小元素的交换，交换的两个元素不一定相邻，中间可能夹杂着和它们相等的元素，所以不稳定。
插入排序
算法思想
基本思想和选择排序类似，也是将整个数组划分为有序和无序两个片段。选择排序注重从无序的后半段里挑出最小（最大）的元素追加到有序部分的末尾，而插入排序注重从无序的后半段随便选一个然后按顺序插入到有序的前半段。所以选择排序重心在从无序的后半段选择，而插入排序重心在于往有序的前半段插入。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public int[] insertionSort(int[] arr){
for(int i=1; i<arr.length; i++){ //外层循环负责从无序的后半段拿出来一个数
int temp = arr[i] ;
int j;
for( j=i-1; j>=0; j--){//内层循环负责将aar[i]插入到前面
if(temp<arr[j]){
arr[j+1] = arr[j] ;
}
else {
arr[j+1] = temp ;
break;
}
}
arr[j+1] = temp ;
}
return arr;
}代码的关键在于需要用一个临时变量将正在比较的无序元素保存起来，然后依次向后移动有序元素，等到找到真正属于它的位置时再将它插入。
代码二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int[] insertionSort2(int[] arr){
for(int i=1; i<arr.length; i++) {
int temp = i ;
for(int j=i-1; j>=0; j--){
if(arr[temp]<arr[j]){
int t = arr[temp] ;
arr[temp] = arr[j] ;
arr[j] = t;
temp=j;
}
}
}
return arr;
}代码的关键在于需要用一个临时变量将正在比较的无序元素保存起来。相比代码一，这里边比较边交换。
复杂度分析
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
是否稳定
稳定
希尔排序
算法思想
希尔排序是个加强版的插入排序。按照不同的步长将元素分组，比如步长为2就代表每隔两个元素为一组，然后对每组进行插入排序，然后不断缩小步长，插入排序，直至步长为1.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int[] shellSort(int[] arr){
for(int gap=arr.length/2; gap>0; gap/=2){ //分成gap组，第gap个元素表示第1组的第二个元素
//进行插入排序,需要注意这里并不是一组一组的排，而是从第gap个一直往后遍历，会轮询对每个组排序，因为从gap往后遍历，遇到的元素要么是从本组第二个元素开始遍历到的，要么是其他组的从第二个元素开始的，所以可以用插入排序。
for(int i=gap; i<arr.length; i++){
int temp = i;
for(int j=temp-gap; j>=0; j-=gap){
if(arr[temp]<arr[j]){
int t = arr[temp] ;
arr[temp] = arr[j] ;
arr[j] = t;
temp=j;
}
}
}
}
return arr;
}复杂度分析
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
是否稳定
不稳定
归并排序
算法思想
典型的分治思想，先将数组一分为二，最每个小数组分别排序，排好之后合并两个小数组得到最终结果。
代码
使用递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public class MergeSort {
public void mergeSort(int[] arr, int temp[], int start, int end){
//先判断数组长度是否大于2
if(end-start<2){
return arr;
}
int mid = start+(end-start)/2 ;
mergeSort(arr, temp, start, mid);
mergeSort(arr, temp, mid, end);
merge(arr, temp, start, mid, end) ;
}
public void merge(int[] arr, int[] res, int start, int mid, int end){
System.arraycopy(arr,start,res,start,end-start);
int i= start;
int j= mid;
int k=start ;
while(i<mid && j < end){
if(res[i] < res[j]){
arr[k++] = res[i++] ;
}
else{
arr[k++] = res[j++] ;
}
}
while(i<mid){
arr[k++] = res[i++] ;
}
while(j<end){
arr[k++] = res[j++] ;
}
}
}这段代码，嗯，有点东西，首先为了严格遵守空间复杂度，临时数组的创建的是在归并排序外面完成的，否则会因为递归不断创建临时数组，空间复杂度就会超过$O(n)$。其次，需要保证我们排序之后引用指向的还是原数组，即排序前后数组引用指向的是同一块空间，这一点也很重要，否则虽然排序效果达到了，但是引用指向的对象早已物是人非，很不优雅。
复杂度分析
时间复杂度：
$$ \begin{equation}
\begin{aligned}
f(n) &= 2f(\frac{n}{2})+\frac{n}{2}\& =2^2f(\frac{n}{2^2})+\frac{2}{2}n\&=2^3f(\frac{n}{2^3})+\frac{3}{2}n\&=2^kf(\frac{n}{2^k})+\frac{k}{2}n\&=n\log{n}+\frac{n}{2}\log{n}\&=O(n\log{n})
\end{aligned}
\end{equation}$$
空间复杂度：$O(n)$
是否稳定
稳定。
快速排序
1. 算法思想
快排的关键在于把枢轴（pivot）放到对应的位置，即枢轴前面的数都比它小，后面的数都比它大。这样枢轴就把整个数组划分成了两部分。那么问题来了，如何把确定枢轴真正的位置呢？即如何把枢轴放到真正的位置呢？
假设对于数组a
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
我们刚开始认为a[0],令x=a[0]是枢轴，那我们分别用j=9从后往前遍历，以及用i=1从前往后遍历。
从后往前遍历时，遇到比x小的则暂时停止，
从前往后遍历时，遇到比x大的则暂时停止，
然后交换i和j位置上的元素，直到i和j相遇，这时的位置就是枢轴的位置，此时交换当前位置元素和枢轴元素。
总结一下，快排的关键在于：从两边向中间进行搜索，以此确定枢轴位置，然后递归进行此方法。
2. 代码
1 | public int quickSort(int[] arr, int left, int right) { |
3. 复杂度分析
快排的时间复杂度取决于枢轴选择的好坏，即划分的位置。从上面代码可以看出，划分操作的时间复杂度是$O(n)$。当划分的两个子数组长度分别是n-1和0时，复杂度最高，递归公式为$T(n)=T(n-1)+T(0)+O(n)$, 解为$O(n^2)$.
当两个数组长度接近等长时，复杂度最低, 递归公式为$T(n)=2T(n/2)+O(n)$, 解为$O(nlogn)$.
堆排序
1. 算法思想
要理解堆排序，首先要理解什么是堆，什么是大顶堆，什么是小顶堆。
首先，堆也是一种二叉树，其次，堆的父节点总是比两个子节点大（大顶堆）或比两个子节点小（小顶堆）。
堆排序的核心在于两点：
- 堆调整：首先将一个无序的数组序列调整成大顶堆，这样一来根节点就是整个序列的最大值了。
- 交换并重新调整：将根节点元素和堆最后一个元素交换，这样一来最后一个元素就是最大的了，剩下的前n-1个元素是无序的，重新调整。
那么就有一个问题了，如何调整？我们从最后一个非叶子节点开始，比较它和它的两个儿子的大小，如果它的儿子比它大，则进行交换。
那么问题又来了，如何确定非叶子节点？学过二叉树性质的朋友应该知道，最后一个非叶子节点的下标应该是$(a.length/2)-1$.
2. 代码
1 | public void heapSort(int[] arr) { |
3. 复杂度分析
计数排序
1. 思想
它不是通过比较进行排序，而是通过额外开辟一块空间，通过下标来暗示这里存的是哪个元素，通过数组值来表示存的这个元素有几个。
具体操作是这样的：
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
代码
1 | public int[] countingSort(int[] arr){ |
3. 分析
这种排序算法适用于那种待排序序列比较集中的情况，这样创建的额外数组空间比较小，节省资源。
它是一种稳定排序。
桶排序
1. 思想
上面的计数排序核心思想在于我们使用一个额外的数组来进行计数，桶排序在思想上和计数排序有所类似，只不过桶排序中的桶直接拿来装待排序的元素了。在桶排序中，我们通过某种映射，把某些元素映射到某些桶里，然后对每个桶中元素进行排序，最后把所有桶连接起来。在这里，对桶中元素排序我们使用稳定的排序方法，如快排，这样最后我们的桶排序也是稳定的。
2. 代码
基数排序
1. 思想
从个位开始，按照每个进制位对元素进行稳定排序。
