【交换排序】快速排序的超详细讲解 | 双边+单边循环图解、分治思想、复杂度详解、以及与冒泡排序算法时间效率的对比 + 完整可运行c语言代码

快速排序

文章目录

• 快速排序
• • 1. 算法思想
  • 2. 双边循环法
  • 3. 单边循环法
  • 4. 额外补充 （分治）
  • 5. 复杂度分析
  • • 5.1 最坏情况
    • 5.2 最好情况
    • 5.3 平均情况
  • 6. 稳定性分析
  • 7. 测试函数
  • 8. 头文件部分
  • 9. 实现
  • • 9.1 双边循环法
    • 9.2 单边循环法
  • 10.测试案例
  • • main函数
    • 输出结果

1. 算法思想

• 快速排序⾸先选⼀个犄点（可以认为是要放到排序后数组正确位置的元素）pivot，然后将数组按照选取的基准 pivot 进⾏划分，⽽选取 pivot 的⽅式⼜有很多种，所以快速排序具有很多版本

总是选择第⼀个元素作为基准 pivot（以这个举例）

总是选择最后⼀个元素作为犄点

随机的选择⼀个元素作为犄点

选择最中间的元素作为犄点

• 快速排序的关键是划分 partion() 。每⼀趟划分，我们就可以将作为 pivot 的值 x 放到排序数组的正确位置，并且将所有⽐ x ⼩的放到 x 的左边，所有⽐ x ⼤的元素放到 x 的右边。⽽且划分操作的时间复杂度是线性的，即O（n）量级！

• 下面我们介绍两种找**犄点(pivot)**的方法，双边循环法，单边循环法

2. 双边循环法

• 首先选择数组的第一个元素38当作犄点， 我们要确定right指针右边的元素都比犄点大，left指针左边的都比犄点小
• 第一步移动right指针，pivot指向的元素和right指针指向的元素进行比较

• 此时right指针指向的元素小于pivot指向的元素，right指针停下，开始移动left指针

• 移动left指针 left指针指向的元素和pivot指向的元素比较，此时left指针指向的元素大于pivot指向的元素，left指针停下

• 交换left指针和right指针的值，继续执行上述过程，移动right指针

• 移动left指针

• 此时left指针和right指针相碰，此时也就找到了最开始选择的 pivot 的正确位置，也就是此时相碰的位置

• 交换 左右指针相碰的位置 和 pivot 指向位置的值

• 此时第⼀趟快速排序结束啦，我们确定了最开始选择的 pivot 的正确位置

接下就是分别对 38 左侧⽐ 38 ⼩的元素 [13,27] ，与右侧⽐ 38 ⼤的元素进⾏快速排序，过程和第⼀趟排序过程⼀样，此处不再赘述 也就是下面这样

• 另外提一嘴必须得是right先找 (留个悬念)

3. 单边循环法

• 首先选择数组的第一个元素38当作犄点

• 指针i用来不断向后遍历 mark用来找到 pivot 的正确位置

• 发现13比38小了

• mark指针往后走一步再与i交换位置 (值交换)

• i指针继续向后遍历 此时27比38小

• mark指针往后走一步再与i交换位置 (值交换)

• i指针继续向后遍历 遍历完了

• pivot指针和mark指针交换位置 (值交换)

• 此时第⼀趟快速排序结束啦，我们确定了最开始选择的 pivot 的正确位置

接下就是分别对 38 左侧⽐ 38 ⼩的元素 [27,13] ，与右侧⽐ 38 ⼤的元素 [97,76,65,49,49] 进⾏快速排序，过程和第⼀趟排序过程⼀样，此处不再赘述 也就是下面这样

4. 额外补充 （分治）

• ⼀趟快速排序结束了。就是将数组按照pivot分成了⼩于等于pivot的⼀组和⼤于pivot的⼀组，可是分治的明显么？好像不明显

快速排序和归并排序(后面将会更新) ⼀样均属于分治算法，分治与递归就是⼀个孪⽣兄弟，提到了分治，怎能缺少递归呢？

递归三要素中最核⼼的就是确定⼀个函数的功能，⽽我们经过上⾯对⼀趟快速排序的介绍，可以发现，之后的每⼀趟快速排序事实上和第⼀趟是⼀样的，也就意味着反复调⽤同⼀个函数存在，即快速排序的过程中蕴含了递归思想，这也是分治的⼀个佐证

但是我们也可以有更清晰的解释，且看下图

• ⾸先根据原始数组 [1,8,3,9,4,5,4,7] ，将数组划分为⼩于等于 7 的数组 [1,3,4,5,4] 和[8,9] ，然后将 [1,3,4,5,4] 根据 4 划分为 [1,3,4] 和 [5] ；将 [1,3,4] 根据 4 划分为[1,3] ；将 [1,3] 根据 3 划分为 [1] ；将 [8,9] 根据 9 划分为 [8] ；这个过程不就是⼆分吗？ (这里我们选择最后一个元素作为 pivot)

的确如此，只不过对于这个数组⽽⾔选择最末尾的元素作为 pivot 得到的树的⾼度并不是我们期望的logn = log8 = 3 ，⽽是 4

说到这⾥，我们顺带说⼀下快速排序的缺点，对于⼀个有序数组 [1,3,4,4,5,7,8,9] ⽽⾔，如

果每次选择最后⼀个元素作为 pivot ，就会得到下⾯⼀幅图：

⽽这时树的⾼度变成了n ，也就意味着快速排序退化成了⼀颗单链，这不是我们希望看到的。但是我们每⼀次选择最中间的元素作为 pivot ，⼜会怎么样呢？

如果将数组 [1,8,3,9,4,5,4,7] 重新调整顺序，使得快速排序的的分治过程如上图所示？看着图就能写出来了，当然答案可能有很多个，最简单的⼀个就是 [1,4,3,5,8,9,7,4]

5. 复杂度分析

• 快速排序的时间通常表示为：T(n) = T(k) + T(n – k + 1) + n

其中 T(k) 和 T(n – k + 1) 分别表示递归调⽤，⽽最后⼀项n表示 将最后⼀个元素作为pivot进⾏划分 的处理过程，k 表示⽐ pivot ⼩的元素的数⽬

⽽快速排序的时间复杂度取决于输⼊的数组和划分策略，所以需要从三个⽅⾯分析：

5.1 最坏情况

我们每⼀次选择最⼤的元素或者最⼩的元素作为 pivot

选择做末尾的元素作为 pivot，最坏情况就是输⼊的待排序数组为有序数组（以升序为例），此时 k = n – 1 ，那么：T(n) = T(n – 1) + T(0) + n ,即T(n) = T(n-1)+n

所以最坏情况下的时间复杂度为O(n^2) 量级

下面来个例子

设对有序数组 [1,3,4,4,5,7,8,9] 进⾏快速排序，每次选择最末尾的元素作为 pivot，那么就会得到下图所示的情况：

• 也就说需要选择 n个 pivot，并且以每⼀个 pivot 进⾏划分需要O(n)的时间，那么总的时间就是O(n^2)量级

5.2 最好情况

当划分过程中每⼀次都能选择最中间的元素作为基准 pivot ，那么快速排序的时间复杂度就等于：T(n) = T(n/2)+T(n/2)+n

其中T(n)表示快速排序的时间复杂度，T(n/2) 表示划分出的两个⼦数组排好序所⽤的时间， n表示 将最后⼀个元素作为pivot进⾏划分 函数的执⾏时间

根据主定理（Master Theorem），快速排序最好情况下的时间复杂度为 O(nlogn).

当然我们也可以换⼀个⻆度来算，⽐如对数组 [1,8,3,9,4,5,4,7] ⽽⾔，我们希望得到的是下⾯⼀幅图

这个树的⾼度就是 O(logn)，也就是选择 pivot 需要O(logn) 次，⽽根据每⼀个 pivot 我们需要 O(n)的时间执⾏划分函数，所以总的时间复杂度为O(nlogn)量级

5.3 平均情况

对于平均时间复杂度分析⽽⾔，我们需要考虑数组的所有可能的排列，并计算出对每⼀个排列所需要的时间，然后求平均，但是实在太复杂了。我们可以考虑⼀个⼀般的假设，⽐如对于⼀个数组⽽⾔， n/10的元素每次⽐选择的 pivot ⼩，⽽ 9n/10的元素⽐ pivot ⼤，那么快速排序的时间复杂为

T(n) = T(n/10) + T(9n/10) + n.

根据主定理，快速排序的时间复杂度依旧是 O(nlogn), 也就意味着只要只要每⼀次不是选择最⼤或者最⼩的元素作为 pivot ，时间复杂度都在O(nlogn) 量级

快速排序的平均时间复杂度为O(nlogn)量级

6. 稳定性分析

• 快速排序是不稳定的，我们把双边循环那里的图稍微往下画一点 只用右边那一部分

• 到这其实就可以了，两个49的位置发生了变化，就说明快速排序是不稳定的了

7. 测试函数

• 这些函数也是之前写的排序算法里用到的，在前面的排序那里都提到过 看懂即可

typedef int keyType;
typedef struct {
keyType key;// 查找表中每个数据元素的关键值
void* data;// 数据的其他区域
}Element;

typedef struct {
Element* data;// 存放查找表中数据元素的首地址
int length;// 查找表的元素个数
}SortTable;
enum sortStatus { success, failed };

void swapElement(Element* a, Element* b);// 交换元素a和元素b
SortTable* generateRandomArray(int n, int low, int high);// 产生随机数范围[low,high]
SortTable* generateLinearArray(int n, int swapTimes);// 参数顺序空间，随机交换swapTimes次 //轻微乱序 整体接近有序
SortTable* copySortTable(SortTable* old);// 拷贝和old一样值的排序表
void releaseSortTable(SortTable* table);
// 排序算法函数的别名
typedef void (*sortHandler)(SortTable*);
// 测试sortName的排序算法
void testSort(const char* sortName, sortHandler sort, SortTable* table);

/* 交换a和b的元素值 */
void swapElement(Element* a, Element* b)
{
Element tmp;
memcpy(&tmp, a, sizeof(Element));
memcpy(a, b, sizeof(Element));
memcpy(b, &tmp, sizeof(Element));
}
/* 产生n个随机数的排序表，值的范围是[low, high] */
SortTable* generateRandomArray(int n, int low, int high) {
SortTable* table = malloc(sizeof(SortTable));
if (table == NULL)
{
fprintf(stderr, "sort table malloc failed!\\n");
return NULL;
}
table->length = n;
table->data = (Element*)malloc(sizeof(Element) * n);
if (table->data == NULL)
{
fprintf(stderr, "element malloc failed!\\n");
free(table);
return NULL;
}
srand(time(NULL) + 1);
for (int i = 0; i < n; ++i)
{
table->data[i].key = (rand() % (high – low + 1)) + low;
table->data[i].data = NULL;
}
return table;
}
/* 产生n个随机交换swapTimes次的有序顺序表 */ //轻微乱序 整体接近有序
SortTable* generateLinearArray(int n, int swapTimes)
{
SortTable* table = malloc(sizeof(SortTable));
if (table == NULL)
{
fprintf(stderr, "sort table malloc failed!\\n");
return NULL;
}
table->data = malloc(sizeof(Element) * n);
if (table->data == NULL)
{
fprintf(stderr, "data malloc failed!\\n");
free(table);
return NULL;
}
table->length = n;
for (int i = 0; i < n; ++i)
{
table->data[i].key = i;
table->data[i].data = NULL;
}
// 在已经有序的排序表中，交换swapTimes次
srand(time(NULL) + 2);
for (int i = 0; i < swapTimes; ++i)
{
int pos1 = rand() % n;
int pos2 = rand() % n;
swapElement(&table->data[pos1], &table->data[pos2]);
}
return table;
}
/* 拷贝一个排序表，使用同样的数据进行不同排序算法的测试 */
SortTable* copySortTable(SortTable* old)
{
SortTable* table = (SortTable*)malloc(sizeof(SortTable));
table->length = old->length;
table->data = malloc(sizeof(Element) * old->length);
for (int i = 0; i < old->length; ++i)
{
table->data[i].key = old->data[i].key;
table->data[i].data = old->data[i].data;
}
return table;
}
/* 释放table */
void releaseSortTable(SortTable* table)
{
if (table) {
if (table->data) {
free(table->data);
}
free(table);
}
}
// 检查排序表里的数据，是否是从小到大排序
static enum sortStatus checkData(const SortTable* table)
{
for (int i = 0; i < table->length – 1; ++i)
{
if (table->data[i].key > table->data[i + 1].key)
{
printf("Check Sort Data Failed: %d : %d\\n", table->data[i].key, table->data[i + 1].key);
return failed;
}
}
return success;
}
/* 测试sortName的排序算法，算法通过sort传递函数名，数据以table传入 */
void testSort(const char* sortName, sortHandler sort, SortTable* table)
{
clock_t start = clock();
sort(table);
clock_t end = clock();
if (checkData(table) == failed)
{
printf("%s failed!\\n", sortName);
return;
}
printf("%s cost time: %fs.\\n", sortName, (double)(end – start) / CLOCKS_PER_SEC);
}

8. 头文件部分

//快排
//双边循环法
void quickSortV1(SortTable* table);
//单边循环法
void quickSortV2(SortTable* table);

9. 实现

9.1 双边循环法

static int partitionDouble(SortTable* table, int startIndex, int endIndex)
{
//犄点 左指针 右指针
int pivot = startIndex;
int left =qidian startIndex;
int right = endIndex;
//随机将startIndex和后续的一个随机索引指向的元素进行交换
while (left != right)
{
//right指针的值大于pivot指针的
while (left<right && table->data[right].key > table->data[pivot].key)
{
right—;
}
//left指针的值小于pivot指针的
while (left < right && table->data[left].key <= table->data[pivot].key)
{
left++;
}
/*执行到这right指针指向的元素小于pivot指向的元素
left指针的指向的元素大于pivot指向的元素
交换left指针和right指针指向的元素*/
if (left < right)
{
swapElement(&table->data[right], &table->data[left]);
}

}

//while 循环出来 left和right指向同一个位置 交换pivot位置和left(right)位置的值
swapElement(&table->data[pivot], &table->data[left]);
//返回正确的pivot的位置
return left;
}

//用递归思想实现[start,end]区间的排序
static void quickSort1(SortTable* table,int startIndex,int endIndex)
{
if (startIndex >= endIndex)
{
return;
}

//找到犄点
int pivot = partitionDouble(table, startIndex, endIndex);
//递归调用
//左
quickSort1(table, startIndex, pivot – 1);
//右
quickSort1(table, pivot+1, endIndex);
}

void quickSortV1(SortTable* table)
{
//递归调用
quickSort1(table, 0, table->length – 1); //用的闭区间
}

9.2 单边循环法

/*这个注释就不写了 其实看懂上面我们画的图这个很好理解的*/
static int partitionSingle(SortTable* table, int startIndex, int endIndex)
{
keyType tmpValue = table->data[startIndex].key;
int mark = startIndex;
for (int i = startIndex + 1;i <= endIndex;i++)
{
if (table->data[i].key < tmpValue)
{
mark++;
swapElement(&table->data[i], &table->data[mark]);
}
}
swapElement(&table->data[startIndex], &table->data[mark]);

return mark;
}

static void quickSort2(SortTable* table, int startIndex, int endIndex)
{
if (startIndex >= endIndex)
{
return;
}

int pivot = partitionSingle(table, startIndex, endIndex);
quickSort2(table, startIndex, pivot – 1);
quickSort2(table, pivot + 1, endIndex);

}

void quickSortV2(SortTable* table)
{
quickSort2(table, 0, table->length – 1);
}

10.测试案例

main函数

void test03()
{
int n = 10000;
// table1: n个随机数的排序表，值的范围是[0, 5000]
// table2: 拷贝table1中的内容
// table3: 拷贝table1中的内容
SortTable* table1 = generateRandomArray(n, 0, 0 + 5000);
SortTable* table2 = copySortTable(table1);
SortTable* table3 = copySortTable(table1);

testSort("bubbleSortV3", bubbleSortV3, table1);
testSort("Quick SortV1",quickSortV1, table2);
testSort("Quick SortV2",quickSortV2, table3);

releaseSortTable(table1);
releaseSortTable(table2);
}

输出结果

bubbleSortV3 cost time: 0.443000s.
Quick SortV1 cost time: 0.001000s.
Quick SortV2 cost time: 0.002000s.

多次测试所得耗时数值不会完全相同 会受很多因素影响

这里就贴个三组数据

感兴趣可以自己测试下

嘻嘻嘻嘻 快速排序部分到此结束😆😆

堆排序 静候更新 👻👻👻😸😸😸

(有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖

持续更新中…