【数据结构】五类八种排序算法_5类排序算法

五类八种排序算法

排序算法种类：

排序算法详情：

• 排序算法的稳定性： 如果数组中有两个3，排序后，这两个3的前后位置可能发生变化，则为不稳定排序。
• 算法的时间复杂度： 算法中运行次数最多的一行的运行次数，如果运行次数最多的一行的运行次数为n的一次幂，则时间复杂度为O(n)。如果是二次幂（类似于n(n-1)/2），就为O（n^2）。
• 算法的空间复杂度： 算法中的临时存储空间，如一般的递归算法有O(n)的空间复杂度，因为每次递归都要存储返回信息。

一、插入排序

①直接插入排序

1、排序行为：

​ 从第2位（1位）开始，如果这一位的值小于上一位，则从这一位开始往前遍历找到适合插入的位置，插入进去，其插入点的后面部分均向后移一位。

2、基本信息：

3、代码实现：

public static void insertSort(int[] array){
    for(int i=1;i<array.length;i++){
        int j=i;
        int target=array[i];//表示想插入的数据
        while(j > 0  && target<array[j-1]){//如果插入的数据小于数组的前一个时
            array[j]=array[j-1];
            j--;
        }
        array[j]=target;
    }
}
1
2
3
4
5
6
7
8
9
10
11

4、适用场景：

​ 数据量大的时候效率很低，直接插入排序适用数据量小的情况。

②希尔排序

1、排序行为：

​ 根据步长排序，每一轮的在该步长的数据都会变为顺序，比如步长为3，则0，3，6，9，12下标的数据，单拎出来是顺序的。然后1，4，7，10，13也一样。

​ 步长会根据一个算法逐渐变为1。

​ 使用while(j>step-1 && target<array[j-step]) 可以防止以前排序后的两个数重复比较。

2、基本信息：

正序效率最高，反序效率最低。

3、代码实现：

 public static void shellSort(int[] array,int step){
    while(step > 1){
        for(int k=0;k<step;k++) {//对步长的定位，选择每次操作的开始位置
             for(int i=k+step;i<array.length;i=i+step){//i表示从第2个数开始插入
                 int j=i;
                 int target=array[i];//表示想插入的数据
                 while(j>step-1  && target<array[j-step]){//如果插入的数据小于数组的前一个时
                     array[j]=array[j-step];
                     j=j-step;
                 }
                 array[j]=target;
             }
         }
        step = step/5 + 1;//这一轮的step全部排序完之后，改变步长继续操作
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、适用场景：

二、选择排序

①简单选择排序

1、排序行为：

​ 双层嵌套循环，每一次都找剩下集合中最小的一个，找到之后与外层循环到的位置的元素互换。

2、基本信息：

3、代码实现：

public static void selectSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int index = i;
        for (int j = i + 1; j < array.length; j++) {
        	//若是从大到小排，则此处改为<
            if (array[j] < array[index]) {
                index = j;
            }
        }
        if (index != i) {
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、适用场景：

​ 同冒泡排序一样，适用数据规模非常小的情况。

②堆排序

1、排序行为：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

相当于从最后一个父结点开始跟子结点比较，和最大的那个子结点换。这个父结点搞定之后，就搞下一个父结点，直到把根节点搞定，就成为了大根堆。

2、基本信息：

3、代码实现：

public static void heapSort(int array[],int len){
    //建堆  len/2-1 是最后一个非叶子结点
    //只有  len/2 个结点才有子结点，所以先就只需要初始化0~len/2-1位，即len/2个
    for(int i=len/2-1;i>=0;i--){
        maxHeapify(array,i,len-1);
    }
    //排序,根节点和最后一个节点交换
    //换完以后，取走根，重新建堆
    //len-1 最后一个节点
    for(int i=len-1;i>0;i--){
        int temp=array[0];
        array[0]=array[i];
        array[i]=temp;
        maxHeapify(array,0,i-1);
    }
}

/**
* 调整堆
*/
private static void maxHeapify(int array[],int start,int end){
    //父亲的位置
    int dad=start;
    //儿子的位置
    int son=dad*2+1;
    while(son<=end){//如果子节点下标在可以调整的范围内就一直调整下去
        //如果没有右孩子就不用比,有的话,比较两个儿子，选择最大的出来
        if(son+1 <= end && array[son]<array[son+1]){
            son++;
        }
        //和父节点比大小
        if(array[dad]>array[son]){
            return;
        }else{//父亲比儿子小，就要对整个子树进行调整
            int temp=array[son];
            array[son]=array[dad];
            array[dad]=temp;
            //递归下一层
            dad=son;
            son=dad*2+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
36
37
38
39
40
41
42
43

4、适用场景：

三、交换排序

①冒泡排序

1、排序行为：

​ 双层嵌套循环，相邻两个元素如果不符合规则就两两换位，一直都是相邻两位互换。

2、基本信息：

3、代码实现：

public static void bubbleSort(int[] array) {
    //此方法为从前往后判断
    for (int i = array.length - 1; i > 0; i--) {
        boolean flag = false;
        //若是从大到小排，则此处改为<
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        if(!flag){
            return;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4、适用场景：

​ 同简单选择排序一样，适用数据规模非常小的情况。

②快速排序

1、排序行为：

​ 一直执行分区域执行快排算法，大至0-n，小至0-1的区域，都要执行快排。
分治，排序，拆分，合并。
归并是：拆分、排序、合并

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BZCeLrmY-1591324997743)(C:\Users\Administrator\Downloads\未命名文件.jpg)]

2、基本信息：

3、代码实现：

//方法一：
public static void quickSort(int[] array, int begin, int end) {
    if (end - begin <= 0) {
        return;
    }
    int x = array[begin];
    int low = begin;
    int high = end;
    //由于会从两头取数据，需要一个方向
    boolean direction = true;
    thisWhile:
    while (low < high) {
        if (direction) {//从右往左找
            for (int i = high; i > low; i--) {
                if (array[i] <= x) {
                    array[low++] = array[i];
                    high = i;
                    direction = false;
                    continue thisWhile;//跳转到thisWhile处，从thisWhile处开始执行
                }
            }
            high = low;//如果上面的if从未进入，让两个指针重合
        } else {
            for (int i = low; i < high; i++) {
                if (array[i] >= x) {
                    array[high--] = array[i];
                    low = i;
                    direction = true;
                    continue thisWhile;
                }
            }
            low = high;
        }
    }
    //把最后找到的值 放入中间位置
    array[low] = x;//array[high]=x同样可以
    //左右两侧进行快排
    quickSort(array, begin, low - 1);
    quickSort(array, low + 1, end);
}
//方法二：
public class kuaipai {
    private static final String START = "startIndex";
    private static final String END = "endIndex";

    public static void main(String[] args) {
        int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1};
//        quickSort(arr, 0, arr.length - 1);
        feiDiGuiQuickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

//方法二：
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        //递归结束条件：startIndex大于或等于endIndex时
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

//方法三：
    /**
     * 快速排序法 递归 分治（双边循环法）
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        //去第一个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            //控制right指针比较，并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //交换left指针比较，并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //交换left和right指针所指向的元素
            if (left < right) {
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;
            }
        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return left;
    }

//方法四：
    /**
     * 快速排序法 递归 单边循环法
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int danPartition(int[] arr, int startIndex, int endIndex) {
        //取第一个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }


//方法三：
    /**
     * 非递归实现快速排序
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    private static void feiDiGuiQuickSort(int[] arr, int startIndex, int endIndex) {
        Stack<Map<String, Integer>> stack = new Stack<>();
        Map<String, Integer> map = new HashMap<>();
        map.put(START, startIndex);
        map.put(END, endIndex);
        stack.push(map);
        while (!stack.isEmpty()) {
            Map<String, Integer> param = stack.pop();
            int pivotIndex = feiDiGuiPartition(arr, param.get(START), param.get(END));

            if (param.get(START) < pivotIndex - 1) {
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put(START, param.get(START));
                leftParam.put(END, pivotIndex - 1);
                stack.push(leftParam);
            }

            if (pivotIndex + 1 < param.get(END)) {
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put(START, pivotIndex + 1);
                rightParam.put(END, param.get(END));
                stack.push(rightParam);
            }
        }
    }

    private static int feiDiGuiPartition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
}

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

4、适用场景：

​ 快速排序适用于数据量大重复数据少数据是顺序存储结构的情况，不适用与链式存储结构。

四、归并排序

1、排序行为：

先拆分，再排序，组合
需要利用一个辅助空间来组合两个数组。

2、基本信息：

3、代码实现：

public static void mergeSort(int array[],int left,int right){
    if(left==right){
        return;
    }else{
        int mid=(left+right)/2;
        //拆分过程
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        //合并过程
        merge(array,left,mid+1,right);
    }
}

private static void merge(int[] array,int left,int mid,int right){
    int leftSize=mid-left;
    int rightSize=right-mid+1;
    //生成数组
    int[] leftArray=new int[leftSize];
    int[] rightArray=new int[rightSize];
    //填充数据
    for(int i=left;i<mid;i++){
        leftArray[i-left]=array[i];
    }
    for(int i=mid;i<=right;i++){
        rightArray[i-mid]=array[i];
    }
    //合并
    int i=0;
    int j=0;
    int k=left;
    //合并数组使其有序
    while(i<leftSize && j<rightSize){
        if(leftArray[i]<rightArray[j]){
            array[k]=leftArray[i];
            k++;i++;
        }else{
            array[k]=rightArray[j];
            k++;j++;
        }
    }
    //填充上面过程未被合并的余下数据
    while(i<leftSize){
        array[k]=leftArray[i];
        k++;i++;
    }
    while(j<rightSize){
        array[k]=rightArray[j];
        k++;j++;
    }
}

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

4、适用场景：

五、基数排序（桶排序、分配式排序）

1、排序行为：

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。解答开篇

定义一个辅助数组： 定义一个一个二维数组来作为辅助存储空间。数组定义容量为a[10] [n]，其中的n尽量大一点。

第一步： 根据个位数把数据存入新定义的数组：把11放入a[1] []中，把100放入a[0] []中，1009放入a[9] []中。

第二步： 把全部的数从数组a中依次放入原数组中，此时个位数已排序完成。

第三步： 根据十位数把数据存入新定义的数据：把21放入a[2] []中，把100放入a[0] []中，1891放入a[9] []中。

第四步： 把全部的数从数组a中依次放入原数组，此时十位数已排序完成。

…

最后一步： 如果全部数的第n位数都为0，且当前已经轮到第n位数，则当前的原数组就是排序完成后的数组，其个位数、十位数、百位数…最后一位数均为排序完成。

下图来自于菜鸟教程

2、基本信息：

3、代码实现：

#include <stdio.h>
#include <stdlib.h>
#include "string.h"
#include <math.h>
#include "malloc.h"

struct AL//定义一个结构体用作辅助存储的存储类型（主要是需要thisIndex字段）
{
    int thisIndex;
    int a[100];
};

void RadixSort(int array[],int n){
    struct AL ALs[10];
    int i,j,k;
    for(i=0;i<10;i++){
        ALs[i].thisIndex = 0;
    }
    printf("\n");
    int p = 1;
    int index = 1;
    while(p){
        p = 0;//如果当前计算到千位，如果有一个值大于一千（有第四位）则pn=1，继续计算，如果判断为0则终止循环。
        //根据数字的一位，存入辅助存储数组
        for(i=0;i<n;i++){
            int mi = 1;
            for(j=0;j<index;j++){
                mi *= 10;
            }
            if(array[i]/(mi/10)>0){
                p++;
            }
            int q = array[i]%mi/(mi/10);
            int in = ALs[q].thisIndex;
            ALs[q].a[in] = array[i];
            ALs[q].thisIndex++;
        }
        k = 0;
        //从辅助存储数组中放入原数组
        for(i=0;i<10;i++){
            int end = ALs[i].thisIndex;
            for(j=0;j<end;j++){
                array[k] = ALs[i].a[j];
                k++;
            }
            ALs[i].thisIndex = 0;
        }
        //排序的位加一，从个位变为十位、从十位变为百位
        index++;
    }
}
main(){
    int array[10] = {10,123,456,54,21,814,23,15,56,5000};
    int i;
    for(i=0;i<10;i++){
        printf("%d   ",array[i]);
    }
    RadixSort(array,10);
    for(i=0;i<10;i++){
        printf("%d   ",array[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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

4、适用场景：

所有数的最大值和最小值所包含的区间比较小的情况。比如最大值为10，最小值为100，其中包含上千个数。

最难的情况是有一个数特别大，比其他的都要大个几千上万倍