快速排序

1.快排的思想

• 先在数据中找一个基准数据 ： 找待排序数据序列的第一个， 随机数， 三位数取中
• 将数据按照基准数据分成两部分，前一段都比基准小，后一段都比基准大。
• 按照同样的思想分别处理前一段和后一段数据。

2.代码的实现（递归版）

• 数据段为start到end之间的数据。先将基准数据(start位置)保存到tmp中，i=start，j = end。 在i<j的时候，重复执行以下两个过程。

1. 通过j从后往前找第一个比基准数据小的数据，找到后就将j位置的值赋值到i位置
2. 通过i从前向后找第一个比基准数据大的数据，找到后就将i位置的值赋值到j位置

• 循环退出（i == j）后，将tmp中的基准数据存储到i位置。

// 时间复杂度 ： O(nlog(n))
// 空间复杂度 ： O(log(n))
// 稳定性 ： 不稳定的
// 根据基准值，找到基准数据应该所在位置，将数据在原始的空间中划分成两部分
void OneQuick(int *arr, int start, int end)
{
int tmp = arr[start];
int i = start, j = end;
while (i < j)
{
while (i < j && arr[j] >= tmp) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= tmp) i++;
arr[j] = arr[i];
}
arr[i] = tmp;
}
//处理前一段和后一段数据 -- 递归
void Quick(int *arr, int start, int end)
{
// 退出的条件
if (end - start < 1) return;
int mid = OneQuick(arr, start, end);
Quick(arr, start, mid - 1); // 递归处理前一段数据
Quick(arr, mid + 1, end); // 递归处理后一段数据
}

• 判断一段数据是否已经处理完的依据就是看这个段中还有几个数据，只要超过一个数据，那就认为并没有处理完成。

3.非递归的实现

• 将Quick方法改非递归（循环实现）。 但是循环体中一次只能处理一部分数据，那剩余部分数据的start， end这一对数据就需要通过其他的数
  据结构（栈和队列）将其保存。

//结构声明
//将要存储的数据段的起始位置和结束位置封装（struct）成一个数据。
typedef struct
{
int start;
int end;
}ElemType; // 这个类型就是将来给栈或者队列中插入数据。

// 空间复杂度： 栈使用的空间决定的 -- O(log(n))
void Quick2(int *arr, int start, int end)
{
Stack st;
InitStack(&st);
ElemType val = { start, end };
Push(&st, val); // 将整个数据段的起始和结束位置Push到栈中
while (!Empty(&st))
{
ElemType data;
Top(&st, &data);
Pop(&st);
int mid = OneQuick(arr, data.start, data.end);
if (mid - data.start > 1)
{
val.start = data.start;
val.end = mid - 1;
Push(&st, val); // mid这个基准数据左边有超过1个的数据
}
if (data.end - mid > 1)
{
val.start = mid + 1;
val.end = data.end;
Push(&st, val); // mid这个基准数据右边有超过1个的数据
}
}
DestroyStack(&st);
}

4.快速排序优化

1. 用随机数来选取基准数据
2. 用三位数取中发来选取基准数据
3. 当待排序序列数据量达到一定数量时，使用插入排序
4. 聚集相等元素

最后

以上就是感性蜗牛为你收集整理的排序算法——快速排序的全部内容，希望文章能够帮你解决排序算法——快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。