几大常用的排序算法

---

一、插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：
在待排序的元素中，假设第一个元素已有序，现将后面的元素与第一个元素作比较，比第一个元素小插入到前面已经排好的序列中，使得前面的元素有序。按照此法对所有元素进行插入，直到整个序列有序为止
动图演示：

代码如下所示：

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                //加不加等号 能取决于这个排序的稳定性
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

       时间复杂度：
                最坏情况下：O(N^2)
                最好情况下：O(N)
       空间复杂度：O(1)
       稳定性：稳定的排序
1
2
3
4
5

这里的稳定性指假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
一个稳定的排序可以变成不稳定的排序，但是一个不稳定的排序无法变成一个稳定的排序

二、希尔排序（缩小增量排序）

希尔排序法又称缩小增量排序。希尔排序的基本步骤是：
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成
动图演示：

先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序
代码如下：

    public static void shellSort(int[] array) {
        int gap = array.length;
        //进行预排序
        while (gap > 1) {
            gap = gap / 2;
            //对每一组进行插入排序
            shell(array,gap);
        }
    }
    private static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在很多书中给出的希尔排序的时间复杂度都不固定

          稳定性：是一个不稳定的排序
1

三、选择排序

每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可
动图演示：

代码如下所示：

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //最小值
            int minIndex = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
         swap(array, i, minIndex);
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

      时间复杂度：O(N^2)
      空间复杂度：O(1)
      稳定性：不稳定
1
2
3

四、堆排序

堆排序可以看之前的这篇博客【数据结构】之优先级队列(堆)

      时间复杂度：O(n*logN)
      空间复杂度：O(1)
      稳定性：不稳定
1
2
3

五、冒泡排序

左右两个相邻元素进行比较并交换
动图演示：

代码如下所示：

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            if(flg == false) {
                return;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

      时间复杂度：最好和最坏情况下都是O(N^2)
      空间复杂度：O(1)
      稳定性：稳定
1
2
3

六、快速排序

6.1 Hoare法

思路如下：
1、选出一个基准key，一般是最左边或是最右边的。
2、定义一个left和一个right，left从左向右走，right从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要right先走；若选择最右边的数据作为key，则需要left先走）。
3、在走的过程中，若right遇到小于key的数，则停下，left开始走，直到left遇到一个大于key的数时，将left和right的内容交换，right再次开始走，如此进行下去，直到left和right最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
4.此时key的左边都是小于key的数，key的右边都是大于key的数
5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
动图演示：

代码如下所示：

    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partitionHoare(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partitionHoare(int[] array,int left,int right) {
        int tmp = array[left];//基准
        int i = left;
        while (left < right) {
            //第一个判断防止数组越界，第二个是从右边找比基准小的
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //第一个也是防止数组出现越界，第二个是从左边找比基准大的
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //左边大的和右边小的进行交换
            swap(array,left,right);
        }
        //将相遇点和基准进行交换
        swap(array,i,left);
        return left;
    }
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

6.2挖坑法

思路：
挖坑法和Hoare法的思路类似
1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
2、定义一个left和一个right，left从左向右走，right从右向左走。（若在最左边挖坑，则需要right先走；若在最右边挖坑，则需要left先走）
后面的过程就和Hoare法类型
动图演示：

代码如下所示：

    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            if(left >= right) {
                break;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            if(left >= right) {
                break;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

快排的优化

1.三数取中法找中间大数字的下标
2.递归到某个小的区间时使用插入排序
整体代码：

    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        if(end-start+1 <= 10) {
            insertSort2(array, start, end);
            return;
        }
        //三数取中  index是中间大的数字 的 下标
        int index = middleNum(array,start,end);
        swap(array,index,start);
        
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static void insertSort2(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int middleNum(int[] array,int left,int right) {
        int mid = left+((right-left) >> 1);
        //int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            if(left >= right) {
                break;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            if(left >= right) {
                break;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
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
63
64
65
66
67
68
69
70
71
72
73
74
75

      时间复杂度： 
               最坏情况下：O(N^2)
               最好情况下：O(N*logN)
               
      空间复杂度：
               最坏情况下：O(N)
               最好情况下：O(logN)           
      稳定性：不稳定                  
1
2
3
4
5
6
7
8

快排的非递归实现

这里我们使用栈来实现非递归的快排

	public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //找基准
        int pivot = partition(array,left,right);
        //基准左边的区间大于left进行入栈
        if(pivot-1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        //基准右边的区间小于right进行入栈
        if(pivot+1 < right) {
            stack.push(pivot+1);
            stack.push(right);
        }
        //判断栈是否为空 
        //不为空出两个下标再对左和右两个下边进行找基准操作重复以上操作直至数组有序为止
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot-1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
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

七、归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
动图演示：

代码如下所示：

    public static void mergeSort(int[] array) {
        mergeFunc(array,0,array.length-1);
    }
    private static void mergeFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeFunc(array,left,mid);
        mergeFunc(array,mid+1,right);
        //左边和右边分解完进行合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmp = new int[right - left + 1];
        int k = 0;
        //确保两个数组都有元素
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        //看两个数组中 还有哪个有数据
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //拷贝回原来的数组
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }
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

    时间复杂度：O(n*logN)
    空间复杂度：O(N)
    稳定性：稳定
1
2
3

归并的非递归实现

    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i=i+2*gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

八、计数排序

1.统计相同元素出现次数根据
2.统计的结果将序列回收到原来的序列中
3.计数排序只适用于范围集中且重复数据较高的数据
动图演示：

代码如下所示：

    public static void countSort(int[] array) {
        int min = array[0];
        int max = array[0];
        //找到最大值和最小值
        for (int i = 0; i < array.length; i++) {
            if(min > array[i]) {
                min = array[i];
            }
            if(max < array[i]) {
                max = array[i];
            }
        }
        //创建一个计数数组
        int[] count = new int[max-min+1];
        for (int i = 0; i < array.length; i++) {
            int index = array[i]-min;
            count[index]++;
        }
        //遍历这个计数数组
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] !=0) {
                array[k] = i+min;
                k++;
                count[i]--;
            }
        }
    }
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

    时间复杂度：O(范围+n)
    范围 = max-min
    空间复杂度：O(范围)
    稳定性：稳定
1
2
3
4

在以上几种排序中属于稳定排序的只有：插入排序、冒泡排序、归并排序、计数排序