1. 排序的概念

1. 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
2. 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
3. 内部排序：数据元素全部放在内存中的排序。
4. 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2. 总览常见的排序算法

3. 直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

public static void insertSort(int []arr){
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0;j--){
                if(arr[j]<arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1]=tmp;
                }else{
                    break;
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

public  static void shellSort(int []arr){
        int gap = arr.length/2;//设置增量初始值
        while(gap>0){
            for(int i=gap;i<arr.length;i++){
                for(int j=i;j>gap-1;j-=gap){
                    if(arr[j]<arr[j-gap]){
                        int tmp =arr[j];
                        arr[j]=arr[j-gap];
                        arr[j-gap]=tmp;
                    }else {
                        break;
                    }
                }
            }
            gap=gap/2;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。

5. 直接选择排序

public static void selectSort(int []arr){
        for(int i=0;i<arr.length;i++){
            int maxi=0;
            int j=0;
            for(j=1;j<arr.length-i;j++){
                if(arr[j]>arr[maxi]){
                    maxi=j;
                }
            }
            int tmp = arr[maxi];
            arr[maxi]=arr[j-1];
            arr[j-1]=tmp;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6. 堆排序

思路：

1. 升序：建大堆，然后将堆顶元素与堆尾元素交换，然后向下调整。
2. 降序：建小堆，然后将堆顶元素与堆尾元素交换，然后向下调整。
3. 注意：堆顶元素与堆尾元素交换完后，堆尾的下标 -1 ,因为此时堆尾即是最值，已经到了排序的目标位置，不需要再动。

public static void shiftDown(int []arr,int root,int len){
        int parent = root;
        int child = parent*2+1;//左孩子
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){
                child=child+1;
            }
            if(arr[child]>arr[parent]){
                int tmp=arr[child];
                arr[child]=arr[parent];
                arr[parent]=tmp;
            }else{
                break;
            }
            parent = child;
            child = parent*2+1;
        }
    }
    public static void heapSort(int []arr){
        int len=arr.length;
        for(int i=(len-1)/2;i>=0;i--){
            shiftDown(arr,i,len);
        }
        int end = len-1;
        while(end>=0){
            int top=arr[0];
            arr[0]=arr[end];
            arr[end]=top;
            end--;//堆尾的下标 -1
            shiftDown(arr,0,end);
        }
    }
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

7. 冒泡排序

public static void bubbleSort(int []arr){
        for(int i=0;i<arr.length-1;i++){
            boolean flag = false;//设置标志，如果某趟没有进行元素的交换，就说明数组已经有序
            for(int j=1;j<arr.length-i;j++){
                if(arr[j]<arr[j-1]){
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                    flag = true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8. 快速排序(递归)

public class Test {
    // Hoare版————以左边为key，一定要从右边开始找，不然循环结束后的那一步交换就会出问题
    public static int partion1(int []arr,int left,int right){
        int key=arr[left];
        int start = left;
        int end = right;
        while(start<end){
            while(start<end&&arr[end]>=key){
                end--;
            }
            while(start<end&&arr[start]<=key){
                start++;
            }
            int tmp = arr[end];
            arr[end]=arr[start];
            arr[start]=tmp;
        }
        arr[left]=arr[end];
        arr[end]=key;
        return end;
    }

    //挖坑法
    public static int partion2(int []arr,int left,int right){
        int pivot=arr[left];
        int start=left;
        int end=right;
        while(start<end){
            while(start<end&&arr[end]>=pivot){
                end--;
            }
            arr[start]=arr[end];
            while(start<end&&arr[start]<=pivot){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[end]=pivot;
        return end;
    }
    //前后指针法————画图理解下代码
    public static void swap(int []arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public static int partion3(int []arr,int left,int right){
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if(arr[cur]<arr[left]){
                prev++;
                if(cur!=prev){
                    swap(arr,cur,prev);
                }
            }
            cur++;
        }
        swap(arr,prev,left);
        return prev;
    }
    public static void insertSortRange(int[] array,int low,int end) {
        for(int i = low+1;i <= end;i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= low ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int medileOfThreeIndex(int []arr,int left,int right){
        int mid=left+(right-left)>>>1;
        if(arr[left]<arr[right]){
            if(arr[mid]<arr[left]){
                return left;
            }else if(arr[mid]>arr[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(arr[mid]<arr[right]){
                return right;
            }else if(arr[mid]>arr[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    public static void quickSort(int []arr,int left,int right){
        if(left>=right){
            return;
        }
        if(right-left+1<=450000){//可以优化区间内的比较速度
            //当在某个区间的时候，进行插入排序，这里就先不写了
            insertSortRange(arr,left,right);
            return;
        }
        //三数取中用来解决递归深度太深的问题
        int index=medileOfThreeIndex(arr,left,right);
        swap(arr,left,index);
        int div = partion2(arr,left,right);
        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);
    }

    public static void quickSortTest(int [] arr){
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序："+(endTime-startTime));
        //System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args) {
        int[] arr = new int[50_0000];
        Random random = new Random();
        //本身 并没有根本上解决 有序情况下  递归深度太深的情况---》根本上解决问题-》尽量让每次划分更均匀
        for (int i = 0; i < arr.length; i++) {
            //arr[i] = i;
            //arr[i] = random.nextInt(50_0000);
        }
        //int []arr = {0,1,2,3,4,5,6,7,8,9};
        quickSortTest(arr);
    }
}

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

总结：

1. 在用 Hoare版找基准时，在以左边为key，一定要从右边开始找，不然循环结束后的那一步就会出问题
2. 运用三数取中可以减少递归的深度。
3. 设置区间运用插入排序，在一定程度上也能减少递归的深度，但是在设置区间的时候，一定要把握好区间的大小，过于大的区间使用插入排序就会使排序的时间复杂度升高。
4. 快排的时间复杂度虽然和堆排序、希尔排序一样，但快排的速度在大多数情况下时优于堆排序和希尔排序
5. 在Hoare、挖坑法、前后指针法这些当中，更推荐使用挖坑法，他是Hoare的升级，理解起来也没有前后指针法那么难。

9. 快速排序(非递归)

思路：非递归的实现一定是建立在一次划分的基础之上，第一次划分之后，将划分后的结果处理之后入栈，然后就根据具体的操作模拟进行入栈出栈就行。

注意：下面的代码中piovt>left+1就是用来判断 piovt 左边是否有超过一个元素，如果超过一个元素的话，就得再进行划分；如果没有超过一个元素，那么这个区间就是有序的，无需再进行划分，即这个区间无需再进行入栈操作。

public static void quickSortNor(int []arr){
        Stack<Integer> stack = new Stack<>();
        int left=0;
        int right =arr.length-1;
        int piovt = partion2(arr,left,right);
        if(piovt>left+1){
            stack.push(left);
            stack.push(piovt-1);
        }
        if(piovt<right-1){
            stack.push(piovt+1);
            stack.push(right);
        }
        while (!stack.empty()){
            right = stack.pop();
            left = stack.pop();
            piovt = partion2(arr,left,right);

            if(piovt>left+1){
                stack.push(left);
                stack.push(piovt-1);
            }
            if(piovt<right-1){
                stack.push(piovt+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

10. 归并排序(递归)

思路：先使每个子序列有序，再使子序列段间有序

//合并函数
private static void merge(int []arr,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int k=0;
        int []newArr=new int[right-left+1];
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                newArr[k++]=arr[s1++];
            }else{
                newArr[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            newArr[k++]=arr[s1++];
        }
        while(s2<=e2){
            newArr[k++]=arr[s2++];
        }
        //将临时数组的值拷贝会原来的数组
        for(int i=0;i<newArr.length;i++){
            arr[left+i]=newArr[i];
        }
    }
    public static void mergeSort(int []arr,int left,int right){
        if(left>=right){//区间内少于两个元素
            return;
        }
        int mid = left+((right-left)>>>1);//找到区间的中点，然后将区间划分
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,right,mid);将区间合并为一个有序的区间
    }
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

11. 归并排序(非递归)

思路：先2个一组进行合并，再4个一组进行合并…
注意：再划分区间的时候，mid和right的值可能超过数组长度，因此要进行修正

private static void merge(int []arr,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int k=0;
        int []newArr=new int[right-left+1];
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                newArr[k++]=arr[s1++];
            }else{
                newArr[k++]=arr[s2++];
            }
        }
        while(s1<=e1){
            newArr[k++]=arr[s1++];
        }
        while(s2<=e2){
            newArr[k++]=arr[s2++];
        }
        for(int i=0;i<newArr.length;i++){
            arr[left+i]=newArr[i];
        }
    }
public static void merageSortNor(int []arr){
        int gap=1;
        while(gap<arr.length){
            for(int i=0;i<arr.length;i+=2*gap){
                int left=i;
                int mid=left+gap-1;
                //修正mid
                if(mid>=arr.length){
                    mid=arr.length-1;
                }
                //修正right
                int right=mid+gap;
                if(right>=arr.length){
                    right=arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap*=2;
        }
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

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

12. 排序算法复杂度及稳定性分析：

最好情况下的时间

平均时间

最坏情况下的时间

空间复杂度

稳定性

13. 其他非基于比较的算法（了解思想即可）

上面的这些排序算法都是基于比较的，下面介绍几种不基于比较的算法。

13.1 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

public static void countSort(int arr[]){
        //先找出数组中的最大值和最小值
        int max=arr[0];
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        //根据最大值和最小值，创建一个临时数组
        int [] count = new int[max-min+1];
        //将arr中的数据统计入count中，值为 i 的数，就存在count数组中下标为 i 的位置
        for(int i=0;i<arr.length;i++){
            count[arr[i]-min]++;
        }
        //根据数组count，将数据有序的还原到arr数组当中
        int index=0;
        for(int i=0;i<count.length;i++){
            while(count[i]>0){
                arr[index]=i+min;
                count[i]--;
                index++;
            }
        }
    }
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（MAX（N,范围）)
空间复杂度：O（范围）
稳定性：稳定（以下面这种方式）

13.2基数排序

链接: 基数排序

13.3 桶排序

链接: 桶排序