各种排序算法

Veröffentlicht am | Bearbeitet am | in
Symbole im Artikel gezählt: 12k | Lesezeit ≈ 11 minuten.

各种排序算法解析和源码

选择排序

将一个序列中最小的元素同未排序序列的第一个进行交换

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
package selectSort;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int arr[] = new int[] {2,1,3,6,4,8,5,9,7};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void selectSort(int[] arr){
        //遍历所有的数
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            //把当前遍历的数和后面所有的数依次进行比较,记录下最下的那个数的下标
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //如果最小的和当前遍历的数的下标不一样(当前遍历的数字不是后面的数字中最小的)
            if(i!= minIndex){
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = 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
package insertSort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = new int[] {9,3,4,1,5,8,2,7,6};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {
        //遍历所有数字
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]<arr[i-1]){
                int temp = arr[i];
                int j;
                //遍历前i-1个已经有序的数字
                for (j = i-1; j >=0&&temp<arr[j]; j--) {
                    //如果遍历到当前数字比temp的数字大,则将这些数字都往后移动一位
                    arr[j + 1] = arr[j];
                }
                //把外层for循环的当前元素放到前一个数字小于它的位置上
                arr[j+1] = 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
package shellSort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[] {8,4,2,5,1,6,9,3,7};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void shellSort(int[] arr) {
        //遍历所有的步长,步长的规则为:初始值为长度/2,后每次除2
        for (int d = arr.length / 2; d > 0; d /= 2) {
            //遍历所有的元素:
            for (int i = d; i < arr.length; i++) {
                //遍历当前组的所有元素
                for (int j = i - d; j >= 0; j -= d) {
                    //如果当前元素大于加上步长的那个元素
                    if (arr[j] > arr[j + d]) {
                        int temp = arr[j];
                        arr[j] = arr[j+d];
                        arr[j+d] = temp;
                    }
                }
            }
            //System.out.println(d);
        }
    }
}

冒泡排序

将数据两两比较，将大的往序列的后面进行交换（如果当前遍历的元素比后一个元素小则位置不变，继续向后遍历，如果当前遍历的元素比后一个元素大，则将当前元素同后一个元素进行交换）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package bubbleSort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[] {5,3,6,1,7,2,8,9,4};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j+1] = 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
package quickSort;

import java.util.Arrays;

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

    private static void quickSort(int[] arr, int start, int end) {
        //满足排序的条件有数字可以排序
        if (start < end) {
            //把数组中的第一个元素作为基准数
            int flag = arr[start];
            int low = start;
            int high = end;
            //当高低指针不重合的情况下一直比较
            while (low < high) {
                //高指针指向的位置的数比基准数大,高指针向低移动一位
                while (low < high && flag <= arr[high]) {
                    high--;
                }
                //高指针位置元素比基准数小,使用高指针元素覆盖低指针元素
                arr[low] = arr[high];
                //如果低指针位置的元素比基准数小,低指针向高移动一位
                while (low < high && arr[low] <= flag) {
                    low++;
                }
                //低指针位置的元素比基准数大,使用低指针的元素覆盖高指针元素
                arr[high] = arr[low];
            }
            //高低指针重合后,将基准数赋给任意指针所指向的位置
            arr[low] = flag;
            //一次排序完成,递归排序
            //处理前半部分
            quickSort(arr,start,low);
            //处理后半部分
            quickSort(arr,low+1,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
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
package mergeSort;

import java.util.Arrays;

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

    public static void mergeSort(int[] arr, int low, int high) {
        int middle = (high+low)/2;
        if (low<high) {
            //处理左边
            mergeSort(arr, low, middle);
            //处理右边
            mergeSort(arr, middle + 1, high);
            //归并
            merge(arr, low, middle, high);
        }
    }

    public static void merge(int[] arr, int low, int middle, int high) {
        //用于存储归并后的临时数组
        int[] temp = new int[high-low+1];
        //记录第一个数组中需要开始遍历的下标
        int i = low;
        //记录第二个数组中需要开始遍历的下标
        int j = middle+1;
        //记录下一个要放入临时数组中的元素应该放到哪个下标
        int index = 0;
        //遍历两个数组取出最小的数字,放入临时数组中
        //条件为两个数组中的元素都没被遍历完
        while (i <= middle&&j<=high) {
            if (arr[i] <= arr[j]) {
                temp[index] = arr[i];
                i++;
                index++;
            }else{
                temp[index] = arr[j];
                j++;
                index++;
            }
        }
        //其中有一个数组中的元素已经遍历完成,处理另一个数组中多于的数据
        while (i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        while (j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        //把临时数组中的数据重新存入原数组
        for (int k = 0; k < temp.length; k++) {
            arr[k + low] = temp[k];
        }
    }
}

基数排序

将数字按照各个位的大小进行排序,并按先进先出的规则,这样排序的结果为:最高位按照顺序排序,最高位相同,按照次高位的顺序排序,一直到按照最低位排序

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
package radixSort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{921, 334, 63, 22, 15,89,77, 475, 875, 54, 76};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        //先找到最大的元素,决定排序多少轮
        int max = Integer.MIN_VALUE;
        for (int i = 0; i <arr.length ; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //求最大数字的位数
        int maxLength = (max+"").length();
        //用于临时存储数据的数组
        int[][] temp = new int[10][arr.length];
        //定义变量存储数组中已经存储的元素的个数(用于确定将下一个数字放到数组中的什么位置)
        int[] counts = new int[10];
        //根据最大长度决定比较的次数,每一轮根据n的值取出不同位的数
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //对每一个数分别计算余数
            for (int j = 0; j < arr.length; j++) {
                int ys = arr[j]/n%10;
                temp[ys][counts[ys]]=arr[j];
                //让数组中的元素个数加1
                counts[ys]++;
            }
            //对每一位排完序后,把数字取出来
            for (int k = 0, s = 0; k < counts.length; k++) {
                //如果对应位里面有数字,将其取出
                if (counts[k] != 0) {
                    for (int l = 0; l < counts[k]; l++) {
                        arr[s] = temp[ k][l];
                        s++;
                    }
                    //把计数数组清空
                    counts[k] = 0;
                }
            }
        }
    }
}

堆排序

将序列构建为一个大顶堆或者小顶堆,然后将堆顶元素放到已排序序列的第一个,然后再将前面的元素进行重新构建,直到所有的元素都有序

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
package heapSort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[] {5,2,6,8,1,9,4,3,7};

        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void maxHeap(int[] arr,int size,int index) {
        //左子节点
        int leftNode = 2*index+1;
        //右子节点
        int rightNode = 2*index+2;
        int max = index;
        //和两个子节点进行对比,找出最大的节点
        if (leftNode<size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode<size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }
        //交换位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //调整完该节点后,可能会对已经调整好的堆造成影响,所以需要重新调整
            maxHeap(arr, size, max);
        }
    }
    private static void heapSort(int[] arr) {
        //从最后一个非叶子节点开始进行调整,调整到根节点
        int start = (arr.length - 1) * 2;
        for (int i = start; i >= 0; i--) {
            maxHeap(arr,arr.length,i);
        }
        //先把数组中的第0个和堆中的最后一个数进行位置交换,再把前面的处理为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            int temp =arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeap(arr,i,0);
        }
    }
}

与数组初始状态无关的排序算法

首先，与初始状态无关分为几种情况

  1. 算法复杂度与初始状态无关；
  2. 元素总比较次数与初始状态无关；
  3. 元素总移动次数与初始状态无关。

以下四种排序方法的算法复杂度与数组的初试状态无关：

一堆（堆排序）乌龟（归并排序）选（选择排序）基（基数排序）友

稍加判断得到，以上三种情况2、3是必定包含在情况1中间的。

  • 堆排序

　　　　思想：首先对初始数组建立最小堆，然后取堆顶元素与堆尾交换，再此堆元素（不含堆尾）再重新构建最小堆，依次循环。

　　　　分析：由于建立最小堆其实就是将初始元素按照规定的准则进行一系列排序（包括层级向下比较、交换），所以如果元素一开始就已经是最小堆则不需要此时的交换且大大减少向下比较次数，

所以堆排序不属于情况二也不属于情况三。

  • 归并排序

　　　　思想：将初试数组划分成N个子数组，两两进行合并排序，然后结果再和其他同级合并后的数组合并知道合并完所有。

　　　　分析：外层递归与初始无关，主要思考合并排序中的比较和交换即可。合并排序思想：将数组A第一个与数组B第一个比较，较小的那一个直接进入result数组并且指针向下移动再与对面数组第一个比较，依次类推，然后将还有剩余的数组内元素全放入result，最后用result将原数组中对应的值一一替换。因此，假设初始数组就是有序的，那么每次合并排序的时的比较次数都仅仅是一个待合并的数组的长度，因此比较次数与初始状态有关，归并排序不属于情况二。

然而，不论一开始的状态如何，最后都是两个数组进入result，移动次数都为两个待合并数组的长度和，然后再将result内元素全部移动到原来数组进行替换。所以元素移动次数与初始状态无关，归并排序属于情况三。

  • 选择排序　　

　　　　思想：i 从头开始，每次遍历之后所有的元素，k 从 i 开始，向后标记最小的元素，循环后如果大于 i ，则与 i 位置元素交换，一直到最后。

　　　　分析：比较次数都是N-1的阶乘，与初始状态无关，所以选择排序属于情况二。

　　　　　　　交换次数当全部已经排序好时则不发生交换，所以选择排序不属于情况三。

  • 基数排序

　　　　思想：将数组从低位到高位，每到一位对应分入10个桶（0-9）中，依次到最高位，由于每上升一位，处于“0号桶”中的数据都会将此位之前的数字排好，以此达到排序效果。

　　　　分析：基数排序中并不发生任何元素之间的比较，所以基数排序属于情况二。

不论初始数组如何排列，都是从个位开始，各自进入自己个位对应的位置，之后也都是一样，所以元素移动次数一样，所以基数排序属于情况三。

综上所述：

1、算法复杂度与初始状态无关的有：选择排序、堆排序、归并排序、基数排序。

2、元素总比较次数与初始状态无关的有：选择排序、基数排序。

3、元素总移动次数与初始状态无关的有：归并排序、基数排序。

Thanks!