快速排序的C语言实现

时间:2022-06-02 09:49:04

快速排序方法对整数序列操作的一种C语言实现

目标

给定一个长度为n的整数序列,将序列从小到大进行排序

原理

  1. 从序列中任选一个值,将原有序列划分为两个子序列,其中,左侧序列中的值均小于该选出的值,右侧序列中的值均大于或者等于该选中的值,该值位于两个子序列交界(既不属于左侧、也不属于右侧);
  2. 分别对左侧、右侧的子序列用同样的方法进行排序;
  3. 将两个子序列以及中心位置的值进行合并,获得最终排序后的结果。

实现

#include <stdio.h>

/**
* 将输入序列划分为两个子序列,并返回中间位置的下标
*
* @param arr 输入划分的输入序列
* @param left 需要划分序列的最左侧元素下标
* @param right 需要划分序列的最右侧位置下标
* @return 找到的中心位置坐标
*/

int partition(int arr[], int left, int right) {
int j = left, i;
int selectedValue = arr[right];
int temp;
// 用j指定预期的中心点位置
// 用游标i从左向右遍历,如果小于选定值,则扔到j指定位置的左侧,否则继续向右
for (i = left; i < right; i++) {
if (arr[i] < selectedValue) {
// 交换i与j位置的值,并更新j指向的位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j++;
}
}
arr[right] = arr[j];
arr[j] = selectedValue;
return j;
}

/**
* 对输入序列进行快速排序
*
* @param arr 待排序数组
* @param left 需要排列位置的最左侧元素下标
* @param right 需要排序位置的最右侧位置下标
*/

void quickSort(int arr[], int left, int right) {
int q;
if (left < right) {
q = partition(arr, left, right);
quickSort(arr, left, q - 1);
quickSort(arr, q + 1, right);
}
}

int main() {
int i = 0;
int a[15] = { 3, 4, 53, 4, 5, 3, 4, 5, 6, 2, 37, -3,-33, 5, 3 };
quickSort(a, 0, 14);
// 输出
for (i = 0; i < 15; i++) {
printf("%d ", a[i]);
}
return 0;
}

运行结果

-33 -3 2 3 3 3 4 4 4 5 5 5 6 37 53

分析

  1. 因为代码中直接在序列原有位置进行排序,所以,可以直接省掉原理第3条中的合并步骤;
  2. 在进行划分时,可以有很多方法找到中间位置,例如从两侧往中间找,分别找到一个大于选定值和一个小于选定值的,进行交换。在本实现中,则从一侧开始找,并用两个下标进行辅助标志预期的中心位置。
  3. 在快速排序方法中,在理想情况下,应该每次都能成功把序列划分成两个长度相等的子序列,此时,其时间复杂度为O(nlogn),而在极端情况下,则每次划分都找到了端点位置,此时,快速排序的时间复杂度将降为O(n^2)