资讯专栏INFORMATION COLUMN

排序算法总结

KoreyLee / 3025人阅读

摘要:如果对空间限制不大,可以使用基数排序等方法降低时间复杂度,这些线性时间排序法是利用了数据的特性达到最佳的效果。

内部排序

以下为基于比较的排序。

一、插入排序 直接插入排序

基本思想:

将元素插入到已经排好序的序列中。第一个元素已经是有序序列,然后比较外围的元素和序列的最后一个元素,判断是否需要插入,如果小,则插入。

时间复杂度:最优 O(n) 最差 O(n^2)

是否稳定:是

    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) 
            for (int j = i - 1; j >= 0; j--)
                if (arr[j + 1] < arr[j])
                    swap(arr, j + 1, j);
    }

改进后的插入排序

比如,用二分查找优化插入排序,因为是要插入到已经排好序的序列当中,所以在查找插入位置这个地方可以用二分查找来优化。

    public int binarySearch(int[] arr, int low, int high, int key) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (key < arr[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }

    public void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++)
            // determine whether to insert
            if (arr[i] < arr[i - 1]) {
                // record the element to insert
                int key = arr[i];
                // find insert index
                int indexInsert = binarySearch(arr, 0, i - 1, arr[i]);
                // move elements
                for (int j = i - 1; j >= indexInsert; j--)
                    arr[j + 1] = arr[j];
                // insert the key
                arr[indexInsert] = key;
            }
    }
二、选择排序 1. 简单选择排序

基本思想:

选出后面最小的元素和前面的交换

时间复杂度: 最优 O(n^2) 最差 O(n^2)

是否稳定:否

    public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int minIndex = i;
            // find the min index
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            if (minIndex != i)
                swap(arr, i, minIndex);
        }
    }

改进后的选择排序

之前的选择排序是一趟只找到最小的,如果一趟可以把最大最小都找出来,就可以将循环的次数减半。

不过在交换时需要注意一种情况,就是第一个元素就已经是最大元素的情况,因为前面已经交换过 i 和 min,所以再交换时就是交换的 n - i - 1 和 min,而不是 max。

    public void selectSort(int[] arr) {

        int n = arr.length;

        for (int i = 0; i < n / 2; i++) {
            int min = i;
            int max = i;
            for (int j = i + 1; j < n - i; j++) {
                // find the min element
                if (arr[j] < arr[min]) {
                    min = j;
                    continue;
                }
                // find the max element
                if (arr[j] > arr[max])
                    max = j;
            }
            swap(arr, i, min);

            if (max != i)
                swap(arr, n - i - 1, max);
            else // the first element is the max element
                swap(arr, n - i - 1, min);
        }
    }
2. 堆排序

基本思想:

堆排序也是一种直接选择排序,因为它也是将排好序的大根堆 or 小根堆的顶部元素逐个和尾部元素交换,也是一种选择。

时间复杂度: 最优 O(nlgn) 最差 O(nlgn) 是一个很优秀的排序算法

是否稳定:否

    public void adjustHeap(int[] arr, int i, int len) {

        int parent = arr[i];

        // start from left child
        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            // find max child (left or right)
            if (k + 1 < len && arr[k + 1] > arr[k])
                k++;
            // compare the parent and its child, but don"t swap
            if (arr[k] > arr[i]) {
                arr[i] = arr[k];
                i = k;
            } else
                break;
        }

        // insert the original parent on index i
        arr[i] = parent;
    }

    public void heapSort(int[] arr) {

        int len = arr.length;

        // adjust heap from the last none-leaf node
        // from bottom to up; from right to left
        for (int i = len / 2 - 1; i >= 0; i--)
            adjustHeap(arr, i, len);

        // swap the top element and the last element
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, i, 0);
            adjustHeap(arr, 0, i);
        }
    }
三、归并排序

基本思想:分治。将两个有序序列合并成一个有序序列,递归进行。需要辅助数组。

时间复杂度: 最优 O(nlgn) 最差 O(nlgn)

空间复杂度

O(n)

是否稳定:是

    /* create an array in advance to avoid creating arrays frequently */
    private void sort(int[] arr) {
        int n = arr.length;
        int[] temp_arr = new int[n];
        mergeSort(arr, 0, n - 1, temp_arr);
    }

    public void mergeSort(int[] arr, int left, int right, int[] temp_arr) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp_arr);
            mergeSort(arr, mid + 1, right, temp_arr);
            merge(arr, left, mid, right, temp_arr);
        }
    }

    public void merge(int[] arr, int left, int mid, int right, int[] temp_arr) {

        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp_arr[t++] = arr[i];
                i++;
            } else {
                temp_arr[t++] = arr[j];
                j++;
            }
        }

        // insert the remaining elements
        while (i <= mid)
            temp_arr[t++] = arr[i++];
        while (j <= right)
            temp_arr[t++] = arr[j++];

        t = 0;
        // copy elements into array
        while (left <= right)
            arr[left++] = temp_arr[t++];
    }
四、交换排序 1. 冒泡排序

基本思想:

总共有 n 个元素,就比较 n - 1 趟,每一趟比较都会将相邻元素进行比较,然后将较大的元素向后放,就像大数沉底,小数像上冒一样。冒泡排序的交换次数等于原始序列的逆序数。

时间复杂度: 最优 O(n) 最差也是平均 O(n^2)

是否稳定:是

    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);
            }
        }
    }

改进后的冒泡排序一

交换过后,会有部分元素是已经排好序了,这一部分再进行比较是没有意义的,可以从这个地方入手改进冒泡排序。

用一个标志位记录最后一次进行交换的位置,这个位置后面的元素是没有进行交换的,说明是已经排好序的,所以不需要再比较。

    public void bubbleSort(int[] arr) {

        int n = arr.length;
        int i = n - 1;
        int pos = 0;

        while (i > 0) {
            for (int j = 0; j < i; j++) {
                pos = 0;
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    pos = j;
                }
            }
            i = pos;
        }
    }

改进后的冒泡排序二

双向冒泡(正反两个方向同时排序),使排序次数几乎减少一半

    public void bubbleSort(int[] arr) {

        int n = arr.length;
        int left = 0;
        int right = n - 1;

        while (left < right) {
            for (int i = left; i < right; i++) {
                if (arr[i] > arr[i + 1])
                    swap(arr, i, i + 1);
            }
            right--;

            for (int i = right; i > left; i--) {
                if (arr[i] < arr[i - 1])
                    swap(arr, i, i - 1);
            }
            left++;
        }
    }
2. 快速排序

基本思想:

根据选择的基准元素进行划分,然后两边都进行排序,再递归进行。需要注意的是,遍历需要从选择的基准元素的反方向开始。

时间复杂度: 最优也是平均 O(nlgn) 最差 O(n^2) 即每次选的基准元素都是最大(小)值

是否稳定:否

    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotLoc = partition(arr, low, high);
            quickSort(arr, low, pivotLoc - 1);
            quickSort(arr, pivotLoc + 1, high);
        }
    }

    public int partition(int[] arr, int low, int high) {
        int pivot = arr[low];

        while (low < high) {
            while (low < high && arr[high] >= pivot)
                high--;
            swap(arr, low, high);

            while (low < high && arr[low] <= pivot)
                low++;
            swap(arr, low, high);
        }

        return low;
    }
外部排序

非基于比较的排序,时间复杂度可以达到 O(n),其实是用空间换时间。

下面列举的都是线性时间排序法

1. 计数排序(Counting Sort)

基本思想:

利用数组下标来排序。但只适合有限数值的数字,序列的数字最大值 k 如果太大,那么开的辅助数组 C[] 就会很大,占用太多空间。
这种思路经常被用到。

时间复杂度: 最优也是平均 O(n + k) 最差 O(n^2) 即每次选的基准元素都是最大(小)值

是否稳定:是

    public int[] countingSort(int[] A, int k) {
        int n = A.length;
        int[] C = new int[k + 1];

        // counting the number of times each element appears in A
        for (int i = 0; i < n; i++) {
            C[A[i]]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i <= k; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[A[i]] - 1] = A[i];
            C[A[i]]--;
        }

        return B;
    }
2. 桶排序(Bucket Sort)

基本思想:

把数组中数据放到有限个桶中,在每个桶中分别进行排序(可以采用任意排序方法)。

模拟画图 ≡ω≡

      input:[12,22,2,13,23,3]

     |     |     |     |     |     |
     | 2,3 |     |12,13|     |22,23|
     |_____|     |_____|     |_____|
     bucket1     bucket2     bucket3
      (1-10)     (11-20)     (21-30)

      output:[2,3,12,13,22,23]   

时间复杂度: 最优近似 O(n) 最差 O(n^2) 即每次选的基准元素都是最大(小)值

是否稳定:是

    public void bucketSort(int[] arr){

        int n = arr.length;

        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num < min)
                min = num;
            if (num > max)
                max = num;
        }

        // create bucket
        int bucketNum = max / 10 - min / 10 + 1;
        List bucketList = new ArrayList>();
        for (int i = 1; i <= bucketNum; i++) {
            bucketList.add(new ArrayList());
        }

        // insert into bucket
        for (int i = 0; i < n; i++) {
            int index = (arr[i] - min) / 10;
            ((ArrayList)bucketList.get(index)).add(arr[i]);
        }

        ArrayList bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList)bucketList.get(i);
            bucketInsertSort(bucket);
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public void bucketInsertSort(List bucket) {
        for (int i = 0; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }
3. 基数排序(Radix Sort)

基本思想:

前面的计数和桶排序都是只能排一个关键字,而基数排序可以排多个关键字。

基数排序分为两种:假设有二元组 (a, b),以 a 为首要关键字,b 为次要关键字排序

MSD(Most Siginificant Digit) 先排 a,后排 b

LSD(Least Siginificant Digit) 先排 b,后排 a

基数排序需要使用稳定的排序算法,一般用计数或者桶排序。

e.g. 采用 LSD

input: [170, 45, 75, 90, 802, 24, 2, 66]

1. 从最后一个关键字开始排:  
   170, 45, 75, 90, 802, 24, 2, 66
     0   5   5   0    2   4  2   6

   排序后(注意保持原来的相对顺序,802 仍然在 2 前面):
   170, 90, 802, 2, 24, 45, 75, 66

2. 从次要关键字开始排
   170, 90, 802, 2, 24, 45, 75, 66
    7   9    0      2   4   7   6

   排序后(170 仍然在 75 前面):
   802, 2, 24, 45, 66, 170, 75, 90

3. 从首要关键字开始排:
   802, 2, 24, 45, 66, 170, 75, 90
   8                   1

   排序后:
   2, 24, 45, 66, 75, 90, 170, 802

output: [2, 24, 45, 66, 75, 90, 170, 802]

时间复杂度:

平均 O(d * (r + n))

d:digit 数字位数 r:radix 基数 n:number 关键字个数

空间复杂度:

O(r + n)

是否稳定:是

    public void radixSort(int[] arr, int n) {

        // find max element
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        for (int k = 1; max / k > 0; k *= 10) {
            countingSort(arr, n, k);
        }
    }

    public void countingSort(int[] arr, int n, int k) {

        // max number is 9
        int C[] = new int[10];

        // counting occurrences
        for (int i = 0; i < n; i++) {
            C[(arr[i] / k) % 10]++;
        }

        // counting elements less than or equal to C[i]
        for (int i = 1; i < 10; i++) {
            C[i] = C[i] + C[i - 1];
        }

        // insert into result array
        int[] B = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            B[C[(arr[i] / k) % 10] - 1] = arr[i];
            C[(arr[i] / k) % 10]--;
        }

        for (int i = 0; i < n; i++) {
            arr[i] = B[i];
        }

    }
总结

关于稳定性:

稳定的排序算法:冒泡、插入、归并、计数、桶和基数排序

不稳定的排序算法: 选择、快速、希尔和堆排序

排序算法的选择:

如果数据有序或基本有序,冒泡和插入的时间复杂度可以降到 O(n),而快排则相反。

如果数据很大,需要考虑使用 O(nlgn) 的排序方法,如快排、归并排序、堆排。

如果对空间限制不大,可以使用基数排序等方法降低时间复杂度,这些线性时间排序法是利用了数据的特性达到最佳的效果。

参考资料:

https://www.byvoid.com/zhs/bl...

https://zh.wikipedia.org/wiki...

https://blog.csdn.net/hguisu/...

https://www.geeksforgeeks.org...

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69574.html

相关文章

  • 各种排序算法总结

    摘要:排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。 排序算法是最基本最常用的算法,不同的排序算法在不同的场景或应用中会有不同的表现,我们需要对各种排序算法熟练才能将它们应用到实际当中,才能更好地发挥它们的优势。今天,来总结下各种排序算法。 下面这个表格...

    null1145 评论0 收藏0
  • 前端 排序算法总结

    摘要:前言排序算法可能是你学编程第一个学习的算法,还记得冒泡吗当然,排序和查找两类算法是面试的热门选项。本篇将会总结一下,在前端的一些排序算法。函数的性能相信对于排序算法性能来说,时间复杂度是至关重要的一个参考因素。 前言 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较你和一个连快排都不会写的人的时...

    happen 评论0 收藏0
  • 算法排序算法总结(JavaScript描述)

    摘要:二代码简单选择排序一分析循环次,每一次的当前项与其之后的项作比较,找出其中最小的那个,与当前项交换。二代码希尔排序是一种改进版的插入排序,缩小增量排序。这样做的目的是因为,直接插入排序在序列基本有序时效率最高。 排序算法 平均情况 最好情况 最坏情况 辅助空间 稳定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 简单选择排序 O(n^2) O(n^2)...

    dkzwm 评论0 收藏0
  • 十大经典排序算法总结(Javascript描述)

    摘要:算法描述冒泡排序是一种简单的排序算法。算法描述和实现一般来说,插入排序都采用在数组上实现。平均情况希尔排序年发明第一个突破的排序算法是简单插入排序的改进版它与插入排序的不同之处在于,它会优先比较距离较远的元素。 前言 读者自行尝试可以想看源码戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 个人博客:Damonare的个人博客 原文地址:...

    Binguner 评论0 收藏0
  • 十大排序算法总结

    摘要:排序算法的稳定性例如排序一个数组,数组中有两个,排序之后是,如果排序之后的两个的前后顺序没有发生变化,那么称这个排序是稳定的,反之则是不稳定的。冒泡排序冒泡排序是很经典的排序算法了,相邻的两个数据依次进行比较并交换位置。 0. 前言 排序算法中涉及到了两个概念: 原地排序:根据算法对内存的消耗情况,可以将算法分为原地排序和非原地排序,原地排序特指空间复杂度为 O(1) 的排序。 排序算...

    王晗 评论0 收藏0
  • 算法-java排序实现总结

    摘要:一常见的排序算法及时间复杂度二各排序算法的理解及实现冒泡排序算法描述比较相邻元素,如果第一个比第二个大,交换位置,这样每经过一趟就冒出一个最大的动图演示代码实现快速排序算法描述从数列中挑出一个元素,称为基准从左向右找比这个第一个比这个基 一.常见的排序算法及时间复杂度 showImg(https://segmentfault.com/img/bV8J6j?w=1722&h=1132);...

    explorer_ddf 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<