文章目录
  1. 1. 简言:
    1. 1.1. 复杂度:
    2. 1.2. 思想:
  2. 2. 原理实现:
    1. 2.1. 基本实现:
    2. 2.2. 优化实现:
  3. 3. 代码实现:

引言:本文介绍快排的思想、代码实现及最基础的优化


简言:

复杂度:

  • 快排最坏情况复杂度O(n²),平均复杂度O(nlogn),是一种不稳定算法。

思想:

  • 快排的思想是:设定序列中一个数(尽量重心)为k,将比k大的数与比k小的数分别放于k的两侧,此时k即归位。
    注:归位是指该元素已在应在的位置,即该元素已排好序

原理实现:

基本实现:

根据《啊哈算法》我们很快就能明白快排是怎么实现的:

  1. 若将一个序列从小到大排序。那么从右往左找比k(通常取a[left])小的(下标记为j),左向右找比k大的(下标记为i),找到就交换a[i]与a[j]。这样保证了让比k小的到左边去,比k大的到右边去。然后进行下一次寻找,再交换。直到i和j碰面(i==j),结束寻找。
  2. 因此推到最后碰面之后,应该让k与a[i]交换,因为此时a[i]比k小(记住我们取a[left]为k),秉承小的放左边的原则,k与a[i]交换。
  3. 为了让一轮最后k成功与a[i]交换,i这个下标在一轮结束前的最后一次交换后就不应该改变。那么我每次应该让j去碰i,即先从右往左找比k大的,这样ij碰在一起i就无法再移动了),交换k和a[i](或k和a[j]是一样的,因为i==j)。这样每次一轮就可以将一个k归位。
  4. 注意:根据上述推理,先从右往左找还是从左往右找,取决于我取的k位于左边还是右边。

但难点在于如何进行优化。上述代码慢就慢在交换i和j需要3次赋值。

优化实现:

  1. 依旧假设从小到大排序。我们从右往左找,找到一个比k小的,我们的目的就是将这个值移到左边去。
  2. 我们的思想是“空缺可填”思想,记住这个思想你将很快理解我在说什么。
  3. 一开始a[left]即a[i]的值已经被装到k里面去了,那么i这个位置就是可填的。一开始,我们从右往左找,找到第一个比k大的,称作a[j],我们把这个数a[j]赋值给a[i],这样j的位置空出来了,j是可填的。然后我们从左往右找,找到第一个比k小的a[i],将a[i]填到j去,现在是i可填了。
  4. 现在想一下是不是一次交换后总是i可填,并且此时a[j]==a[i]?
  5. 那么可以预见一轮下来,a[j]放的肯定是比k大的值,而i的位置空了出来,还没来及去填比k小的,那正好填k。
  6. 接着考虑,如果让i先走,去碰j,那么一轮最后我保留的是j的坐标,同理让j先走保留的是i的坐标,因此j先走,和我们一开始的预设一致。
  7. 如此反复几轮,便完成了排序。

代码实现:

优化后代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<stdbool.h>
int a[10] = { 6,1,2,7,9,3,4,5,10,8 };
void quicksort(int left, int right)
//每一轮将满足条件的a[j]移到左边,将满足条件的a[i]移动右边,最终i==j时将a[i]归位为key
{
if (left >= right)
return;
int key = a[left], t, i = left, j = right;

while (i<j)
{
while (a[j] >= key && j>i)
j--;
a[i] = a[j];
while (a[i] <= key && j>i)
i++;
a[j] = a[i];
}
a[i] = key;
quicksort(left, i - 1);,
quicksort(i + 1, right);
}
int main(void)
{
quicksort(0, 9);
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
return 0;
}
文章目录
  1. 1. 简言:
    1. 1.1. 复杂度:
    2. 1.2. 思想:
  2. 2. 原理实现:
    1. 2.1. 基本实现:
    2. 2.2. 优化实现:
  3. 3. 代码实现: