简述
排序算法在各种各样的题中出现的蛮多的，不管是算法的编程题还是问时间复杂度之类的题目，虽然之前考研的时候都考过，不过那个时候自己也没有动手去实践，这么多排序算法放在一起，我也经常弄混，前两天就狠下心决定把所有的排序算法统统都实践一遍，并且记录下来，其中时间复杂度，空间复杂度和稳定性的分析我都放到注释中去了，希望以后再碰到的时候能够不要再忘记了。
插入排序
插入排序是一种简单直观的排序算法，其基本思想在于每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。
直接插入排序
直接插入排序是一种最简单也是最直观的插入算法。其具体过程如下：假设在排序过程中，待排序表L[1…n]中，前i-1个元素都是已经排好序的时候，将第i个元素插入其中，这样循环下来，就可以让整个排序表有序。其中插入的操作可以如下:
- 查找出L(i)在L[1…i-1]中的插入位置k。
- 将L[k…i-1]中所有元素全部后移一个位置。
- 将L(i)复制到L(k)。
1 | /** |
希尔排序
希尔排序，又称为缩小增量排序。
希尔排序的基本思想是：先将待排序表分割成若干个中间相差d的子表，然后分别进行插入排序，而当整个表中的元素已经基本有序的时候，再对全体记录进行一次直接插入排序。希尔排序的算法如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* 排序名称:希尔排序
* 空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)
* 时间效率:希尔排序的时间复杂度依赖于增量序列函数，其时间复杂度是并不一定的，当
* 数组长度n在一定范围内的时候，时间复杂度约为O(n^1.3)，而最坏情况下则会达到O(n^2)
* 稳定性: 当相同关键字的记录被划分到不同的子表的时候，可能会改变它们之间的相对次序，所
* 以希尔排序是个不稳定的排序算法
*/
public static void shellSort(int[] array){
int i,j,k,temp;
for (int gap=array.length/2;gap>0;gap/=2){
for (i=0;i<gap;i++){
for (j=i+gap;j<array.length;j+=gap){
if (array[j]<array[j-gap]){
temp=array[j];
for (k=j-gap;k>=0&&temp<array[k];k-=gap){
array[k+gap]=array[k];
}
array[k+gap]=temp;
}
}
}
}
}
交换排序
所谓的交换，就是根据序列中两个元素关键字的比较结果来兑换这两个记录在序列中的位置。基于交换的排序算法有很多，常用的主要是冒泡排序和快速排序。其中冒泡排序比较简单，而快速排序则使用的非常的广泛，因为它在大部分的应用场景下效果都是很好的。
冒泡排序
冒泡排序算法的基本思想是：假设待排序表长为n，从后往前两两比较相邻元素的值，如果是逆序，就可以将他们进行交换，这样序列比较完一次就可以称之为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置，而在下一趟排序的时候，前一趟已经确定的元素就不会继续进行排序。这样通过n-1趟就能将整个序列变得有序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 排序名称:冒泡排序
* 空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)
* 时间效率: 当进行n-1趟比较，并且每一趟都进行i次比较的时候，时间复杂度为O(n^2)
* 稳定性: 由于当两个元素相等时并不发生交换，所以冒泡排序是一个稳定的排序算法。
*/
public static void bubbleSort(int[] array){
int temp;
for (int i=0;i<array.length-1;i++){
for (int j=array.length-1;j>i;j--){
if(array[j]<array[j-1]){
temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
}
快速排序
快速排序是对冒泡排序的一种改进。其基本思想是基于分治法的。每次在待排序列表中找出一个元素pivot作为基准，通过一趟排序将待排序表划分为两个独立的部分，其中一边是全大于pivot的元素，而另一边则是全小于pivot的元素，这样递归的做下去，就可以使所有元素都放到其最终位置。
具体的代码如下：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
36/**
* 排序名称:快速排序
* 空间效率:快速排序是递归的，需要借助一个递归的栈来保存每一层递归的信息。
* 其容量应该与递归调用的最大深度是一致的。在最坏情况下，栈的深度是O(n)，而在平均情况下
* 栈的深度为O(logN)
* 时间效率: 快速排序的运行时间与划分是否对称有关系，在通常情况下，时间复杂
* 度为O(nlogN)，而在最坏情况下则会达到O(n^2)
* 稳定性: 划分算法中，若右端区间存在两个关键字相同，切均小于基准值的记录，则在
* 交换到左端区间后，它们的相对位置会发生变化，也就是说快速排序是一个不稳定的排序算法。
*/
public static void quickSort(int[] array,int start,int end){
if(start<end){
int pivotpos=partition(array,start,end);
quickSort(array,start,pivotpos-1);
quickSort(array,pivotpos+1,end);
}
}
/**
* 这是快速排序的辅助函数，用来找出每一次划分的位置，并且确定该划分元素在待排序列中的最终位置
*/
public static int partition(int[] array,int start,int end){
int povit=array[start];
while (start<end){
while (start<end&&array[end]>=povit) {
--end;
}
array[start]=array[end];
while (start<end&&array[start]<=povit){
++start;
}
array[end]=array[start];
}
array[start]=povit;
return start;
}
选择排序
选择排序的基本思想是：每一趟(例如第i趟)在后面n-i+1个待排序元素中选择关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个就不用再选了。
简单选择排序
简单选择排序的基本思想是：假设排序表为L[1…n],第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的位置，这样经过n-1趟排序就可以使整个排序表有序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* 排序名称:简单选择排序
* 空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)
* 时间效率: 简单选择排序中过程中，元素移动的操作次数很少，最好的情况下移动0次
* 此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，时间复杂度始终是O(n^2)
* 稳定性: 在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同
* 关键字元素的相对位置发生改变。简单选择是一个不稳定的排序算法。
*/
public static void selectSort(int[] array){
for (int i=0;i<array.length-1;i++){
int min=i;
for (int j=i+1;j<array.length;j++){
if (array[j]<array[i]) min=j;
}
if (min!=i){
int temp=array[min];
array[min]=array[i];
array[i]=temp;
}
}
}
堆排序
堆排序是一种树形选择排序算法，它的特点是:在排序过程中将待排序表看成是一个二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前的无序区中选择关键字最大（或者最小）的元素。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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/**
* 堆排序
*/
private static void heapSort(int[] array) {
buildMaxHeap(array,array.length);
// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
for (int i = array.length - 1; i > 0; i--) {
swap(array, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
heapAdjust(array, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
}
}
/**
* 初始化一个大顶堆
* @param array
* @param len
*/
public static void buildMaxHeap(int[] array,int len){
for (int i=len/2;i>=0;i--){
heapAdjust(array,i,len);
}
}
/**
* 构建堆的过程
* @param arr 需要排序的数组
* @param i 需要构建堆的根节点的序号
* @param n 数组的长度
*/
private static void heapAdjust(int[] arr, int i, int n) {
int child;
int father;
for (father = arr[i]; leftChild(i) < n; i = child) {
child = leftChild(i);
// 如果左子树小于右子树，则需要比较右子树和父节点
if (child != n - 1 && arr[child] < arr[child + 1]) {
child++; // 序号增1，指向右子树
}
// 如果父节点小于孩子结点，则需要交换
if (father < arr[child]) {
arr[i] = arr[child];
} else {
break; // 大顶堆结构未被破坏，不需要调整
}
}
arr[i] = father;
}
// 获取到左孩子结点
private static int leftChild(int i) {
return 2 * i + 1;
}
// 交换元素位置
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
归并排序
归并排序与上述的交换，选择等排序的思想是不一样的。归并的意义是将两个或者两个以上的有序表组成一个新的有序表。通过递归的方法来完成整个排序的操作。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/**
* 排序名称:归并排序
* 空间效率:merge操作中，辅助空间要占用n个单元，空间复杂度为O(n)
* 时间效率: 每一趟归并的时间复杂度为O(n),算法的时间复杂度为O(n*logN)
* 稳定性: 由于merge操作不会改变相同关键字记录的相对次序，所以二路归并排序算法是一个
* 稳定的算法
*/
public static void mergeSort(int[] array,int start,int end){
if (start<end){
int mid=(start+end)/2;
mergeSort(array,start,mid);
mergeSort(array,mid+1,end);
merge(array,start,mid,end);
}
}
/**
* 归并排序的辅助函数，作用是将两个有序的数组合并到同一个数组中去
*/
public static void merge(int[] array,int start,int mid,int end){
int i,j,k;
int[] tempArray=new int[array.length];
for (i=0;i<array.length;i++){
tempArray[i]=array[i];
}
for (i=start,j=mid+1,k=start;i<=mid&&j<=end;k++){
if(tempArray[i]<tempArray[j]){
array[k]=tempArray[i++];
}else {
array[k]=tempArray[j++];
}
}
while (i<=mid) array[k++]=tempArray[i++];
while (j<=end) array[k++]=tempArray[j++];
}