Fork me on GitHub

常见排序算法

发表于 | 分类于 |
字数统计: 1.4k | 阅读时长 ≈ 6

常见排序算法

排序算法中几个概念

  1. 稳定性：两个相等的数在排序前后”相对位置”不变，则算法稳定。
    稳定性得好处：从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。

  2. 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
    T(n) = O(f(n)) // n 计算次数

  3. 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
    S(n) = O(f(n))

    各种算法稳定性

    1、堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法；
    2、基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

1. 选择排序

算法描述：在未排序序列中找到最小（大）元素，将其存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，

该算法在给定的数组中维护了连个子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectionSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        int temp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = temp;
    }
}

时间复杂：O(n^2)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void selectionSortStable(int[] a) {
       int n = a.length;
       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;
           for (int j = i + 1; j < n; j++) {
               if (a[j] < a[minIndex]) {
                   minIndex = j;
               }
           }
           int minimum = a[minIndex];
           while (minIndex > i) {
               a[minIndex] = a[minIndex - 1];
               minIndex--;
           }
           a[i] = minimum;
       }
   }

2. 冒泡排序

算法描述：冒泡排序是最简单的排序算法，如果它们的顺序错误，可以反复交换相邻的元素，重复进行直到没有交换。

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

时间复杂：O(n^2)
空间复杂度：O(1)
上面实现 时间复杂度始终是 O(n^2)
其实当没有元素进行交互，说明已是有序数组，可以及时跳出循环。
递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSortRecursive(int[] a, int n) {
        if (1 == n) {
            return;
        }
        for (int j = 0; j < n - 1; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        bubbleSortRecursive(a, n - 1);
    }

3. 插入排序

算法描述：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int[] a) {
       int n = a.length;
       for (int i = 1; i < n; i++) {
           int current = a[i]; // 当前选中元素
           int j = i - 1; // 前一个元素下标
               a[j + 1] = a[j];
               j--;
           }
           a[j + 1] = current;
       }
   }

4. 归并排序

算法描述：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

详细分解：把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归排序；
将两个排序好的子序列合并成一个最终的排序序列。

图解如下：

sort_merge

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
	void mergeSort(int[] a, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            mergeSort(a, l, m);
            mergeSort(a, m + 1, r);
            merge(a, l, m, r);
        }
    }

void merge(int[] a, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        /* 创建左右零时数组 */
        int L[] = new int[n1];
        int R[] = new int[n2];
        /*将数组左右部分拷贝到零时数组*/
        for (int i = 0; i < n1; ++i) {
            L[i] = a[l + i];
        }
        for (int j = 0; j < n2; ++j) {
            R[j] = a[m + 1 + j];
        }
        int i = 0, j = 0;
        int k = l;
        /*将左右两数组有序合并*/
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                a[k] = L[i];
                i++;
            } else {
                a[k] = R[j];
                j++;
            }
            k++;
        }

        /* 将L[]剩余元素拷贝到 数组 */
        while (i < n1) {
            a[k] = L[i];
            i++;
            k++;
        }

        /* 将R[]剩余元素拷贝到 数组*/
        while (j < n2) {
            a[k] = R[j];
            j++;
            k++;
        }
    }

5. 快速排序

算法描述：它选择一个元素作为枢轴(pivot)，并围绕拾取的枢轴分割给定的数组。

详细分解：

  1. 从数组挑出一个元素，枢轴（pivot），可以始终选择第一个（最后一个|随机|中位数）元素作为枢轴。

    1. 分区，将比枢轴值小的摆放在枢轴前面，所有元素比枢轴值大的摆在枢轴的后面（相同的数可以到任一边）

  2. 递归地（recursive）把小于枢轴值元素的子数列和大于枢轴值元素的子数列排序。

图解：

​ sort_quick

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
quickSort(int a[], int l, int r) {

        if (l < r) {

            int partitionIndex = partition(a, l, r);



            // 递归左右两边分区排序

            quickSort(a, l, partitionIndex - 1);

            quickSort(a, partitionIndex + 1, r);

        }

    }


int partition(int a[], int l, int r) {
        int pivot = a[r];
        int i = (l - 1); // 比枢轴元素小的游标
        for (int j = l; j < r; j++) {
            if (a[j] <= pivot) {
                i++;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        // 将枢轴元素插入中间
        int temp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = temp;

        // 返回当前枢轴元素下标
        return i + 1;
    }
onlythinking wechat
编程学习探讨，技术不限Java，golang，JavaScript，mysql。编程悟道。多年程序老鸟，欢迎来骚