排序算法集锦

概括

排序算法:

  • 比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。
  • 非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等。

排序性能比较

排序方法 平均情况 最好情况 最坏情况 空间 稳定性
冒泡 O(n2) O(n) O(n2) O(1) 稳定
简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
直接插入排序 O(n2) O(n) O(n2) O(1) 稳定
希尔排序 O(nlogn) ~ O(n2) O(n1.3) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定

冒泡排序

思想: 每次比较相邻两个数,大的往后移

void bubble(int *nums, int len) {
    /*
     * 19, 1, 3, 2, 3, 76, 3, 29, 54
     *
     * 1 19 3 2 3 76 3 29 54
     * 1 3 19 2 3 76 3 29 54
     * 1 3 2 19 3 76 3 29 54
     * 1 3 2 3 19 76 3 29 54
     * 1 3 2 3 19 76 3 29 54
     * 1 3 2 3 19 3 76 29 54
     * 1 3 2 3 19 3 29 76 54
     * 1 3 2 3 19 3 29 54 76
     * .....
     */
    for (int i = 0; i < len - 1; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (nums[j] > nums[j + 1]) {
                int a = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = a;
            }
        }
    }
}


图片来源网络

快速排序

思想:

  • 找一个基准
  • 从右向左找小于等于基准的数停下
  • 从左向右找大于等于基准的数
  • 交换两个位置的数
  • 继续找,知道两位置重合的位置P
  • 交换基准和P位置的两个数
  • 继续开始元素到P-1位置, 继续P+1到最后一个元素位置
  • 如果开始位置大于结束为止,停止
void quickSort(int *nums, int left, int right) {
    if (left > right)
    {
        return;
    }

    int tmp = nums[left];
    int start = left;
    int end = right;

    while (start != end) {
        while (start < end && tmp <= nums[end]) {
            end --;
        }

        while (start < end && tmp >= nums[start]) {
            start ++;
        }

        if (start < end)
        {
            int b = nums[start];
            nums[start] = nums[end];
            nums[end] = b;
        }
    }

    nums[left] = nums[start];
    nums[start] = tmp;

    sort(nums, left, start -1);
    sort(nums, start + 1, right);
}


图片来源网络

声明:原创文章,版权所有,转载请注明出处,https://litets.com。