❤️C语言快速排序算法 ❤️

小蚂蚁

❤️快速排序算法（QSort，快排）及C语言实现

• 
  
• 
  
• ​​1.定义​​
  
• ​​2.基本思想​​
  
• ​​3.步骤​​
  
• ​​4.代码实现​​
  
• ​​5.总结​​
  
• 
  

本节介绍一种排序算法——​​快速排序算法​​（Quick Sort）。

C语言中自带函数库中就有快速排序——qsort函数 ，包含在 <stdlib.h> 头文件中。

1.定义

快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。

2.基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3.步骤

a. 先从数列中取出一个数作为基准数。
b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
c. 再对左右区间重复第二步，直到各区间只有一个数。

4.代码实现

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>#include <string.h>#include <time.h>#include <stdlib.h>//两数交换void swap(int arr[], int i, int j) {  if (i != j) {  arr[i] = arr[i] ^ arr[j];  arr[j] = arr[i] ^ arr[j];  arr[i] = arr[i] ^ arr[j];  }}//这是一个处理arr[L..R]的函数//默认以arr[r]做划分，arr[r] -> p  <p  ==p  >p//返回等于区域（左边界，右边界），返回一个长度为而的数组res, res[0],res[1]int* partition(int arr[],  int L, int R) {  int less = L - 1;// <区域右边界  int more = R;// >区域左边界  static int res[2];//返回数组  while (L < more ){//L表示当前数的位置 arr[R] -> 划分值  if (arr[L] < arr[R]) {  //当前数小于划分值    swap(arr, ++less, L++);  }  else if (arr[L] > arr[R]) {//当前数大于划分值    swap(arr, --more, L);  }else {    L++;  }  }  swap(arr, more, R);  res[0] = less + 1;  res[1] = more;  return res;}//arr[L..R]排序void quickSort(int arr[], int L, int R) {  if (L < R) {  swap(arr, (int)(L + (rand() % (R - L + 1))),R);//取随机位数与最后一位交换，将算法的时间复杂度优化为O(nlogn)  int *p = partition(arr, L, R);  quickSort(arr, L, p[0] - 1);// < 区  quickSort(arr, p[1] + 1, R);// > 区  }}void quick(int arr[], int length) {  if (length < 2) {  return;  }  quickSort(arr, 0, length - 1);}int main() {  int arr[] = {49,38,65,97,76,13,27 };  int length = sizeof(arr) / sizeof(arr[0]);  printf("排序前：");  for (int i = 0; i < length; i++) {  printf("%d\t", arr[i]);  }  time_t start_t = time(NULL);//开始执行时间  mergeSort(arr, length);  time_t end_t = time(NULL);  int t = time(&end_t) - time(&start_t);  printf("\n执行耗时：%d ms\n排序后：", t);  for (int i = 0; i < length; i++) {  printf("%d\t",arr[i]);  }  return 0;}

运行结果为：

5.总结
快速排序算法的​​时间复杂度​​​为​​O(nlogn)​​，是所有时间复杂度相同的排序方法中性能最好的排序算法。
作者：香芋味的猫丶