1. 快速排序
  2. 选择排序
  3. 冒泡排序
  4. 插入排序
  5. 归并排序

快速排序

分治算法。

Powered by MSPaint(((

时空复杂度:

  • 平均情况时间复杂度 $O(n \log n)$
  • 最坏情况时间复杂度 $O(n^2)$
  • 空间复杂度 $O(n)$

基本思想为:

  • 选取一个基准值
  • 将小于或等于基准值的放在基准值左边,将大于基准值的放在基准值右边
  • 对左右进行重复操作,如果左右仅有一个元素或不含元素,当前部分排序完成

实现代码:

// 对 arr\[start..end\] (包含end)进行分割操作,返回分割后基准值的下标
int partition(int arr\[\], int start, int end) {
    int pivot = arr\[start\]; // 选取第一个值为基准值
    int i = start;
    int j = end;

    while (i < j) { // 循环直到分割完毕(i 遇上 j) 
        while (j > i && arr\[j\] >= pivot) {  // 从 j 开始往前寻找一个比基准值小或等于的值
            --j;
        }

        arr\[i\] = arr\[j\]; // 将小于等于的值移到前面 

        while (j > i && arr\[i\] < pivot) {  // 从 i 开始往后寻找一个比基准值大的值
            ++i;
        }


        arr\[j--\] = arr\[i\]; // 将大于的值移到后面,并 j++ 进行下一轮判断 
    }

    arr\[i\] = pivot; // 将基准值放入数组中间 
    return i;
}

// 进行快排
void qsort(int arr\[\], int start, int end) {

    if (end > start) {
        // 对数组进行分割 
        int q = partition(arr, start, end);

        // 对前后两部分进行排序 
        qsort(arr, start, q - 1);
        qsort(arr, q + 1, end);

    }
}

优点:

  • 一般情况下最高效的排序算法
  • 空间复杂度为 $O(n)$

缺点:

  • 对于某些数据(如有序数据),效率不如其他排序算法
  • 是一种不稳定的排序算法

# sort   # 排序   # 算法  


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!