【408数据结构与算法】—快速排序（十九）

【408数据结构与算法】—快速排序（十九）

一、🤣快速排序的基本思想

• 任取一个元素（如：第一个）为中心
• 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表
• 对各子表重新选择中心元素并依此规则调整
• 直到每个子表的元素只剩一个

二、😛快速排序演示

基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边

（枢轴）中间数：可以是第一个数，最后一个数、最中间一个数、任选一个数等

快速排序的特点

每一趟的子表的形成是采用从两头向中间交替式逼近法

快排算法

C语言实现快排

快排是在每轮挑选一个基准元素，并让其比他大的元素移动到数列一边，比他小的元素移动到数列的另一边，从而把数列拆解成两个部分，即分治思想。然后运用递归。

代码演示

#include <stdio.h>
void quickSort(int array[], int left, int right);
int main(void)
{
  int i;
  int array[] = { 5,4,3,2,1,10,9,8,7,6 }; //待排序数组
  int len = sizeof(array) / sizeof(int);  //数组的长度
  quickSort(array, 0, len - 1); //排序
  for (i = 0; i < 10; i++)  //打印排序后的数组
    printf("%d\n", array[i]);
  return 0;
}
void quickSort(int array[], int left, int right)
{
  int i, j, key;
  if (left >= right)
    return;
  i = left; j = right;
  key = array[i]; //取最左边的元素作为key
  while (i < j)
  { //始终保持i < j
    while (i < j && array[j] > key)//右指针向左
      j--;
    if (i < j)  //小于key的放左边
      array[i++] = array[j];
    while (i < j && array[i] < key)//左指针向右
      i++;
    if (i < j)  //大于key的放右边
      array[j--] = array[i];
  }
  array[i] = key; //最终将key放入i==j处
  quickSort(array, left, i - 1);  //左边递归
  quickSort(array, i + 1, right); //右边递归
}

快速排序算法分析

时间复杂度

空间复杂度

• 快速排序不是原地排序
• 由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度（即使不用递归，也需要使用用户栈）
• 在平均的情况下，需要O(logn)的栈的空间
• 最坏的情况下：栈空间可达O(n）

快速排序的稳定性

快速排序是一种不稳定的排序算法

思考题

由于每次枢轴记录的关键字都是大于其他所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时候已经退化成为没有改进措施的冒泡排序。

快速排序不适于对原本有序或基本有序的记录序列进行排序。

快速排序算法分析

• 划分元素的选取是影响时间性能的关键
• 输入数据次序越乱，所划分元素值的随机性越好，排序速度越快，快速排序不是自然排序的方法
• 改变划分元素的选取方法，至多只能改变算法平均情况下的世界性能，无法改变最坏情况下的时间性能。即最坏的情况下，快速排序的时间复杂性总是O(n^2)

👏👏👏总结