个人中心
gpt4 book ai didi

C/C++实现快速排序算法的思路及原理解析

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 40 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C/C++实现快速排序算法的思路及原理解析由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

快速排序

1. 算法思想

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序.

2. 实现原理

2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。 2.2、整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 。

  • 默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
  • 因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
  • 此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
  • 循环 2-3 步骤，直到 low=high，该位置就是基准位置。
  • 把基准数据赋给当前位置。

2.3、第一趟找到的基准位置，作为下一趟的分界点。 2.4、递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。 2.5、最终就会得到排序好的数组.

3. 动态演示

C/C++实现快速排序算法的思路及原理解析

C/C++实现快速排序算法的思路及原理解析

4. 完整代码

三个函数 基准插入函数：int getstandard(int array[],int low,int high) （返回基准位置下标） 递归排序函数：void quicksort(int array[],int low,int high) 主函数：int main() 。

?
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <stdlib.h>
 
void display( int * array, int size) {
   for ( int i = 0; i < size; i++) {
     printf ( "%d " , array[i]);
   }
   printf ( "\n" );
}
 
int getstandard( int array[], int i, int j) {
   // 基准数据
   int key = array[i];
   while (i < j) {
     // 因为默认基准是从左边开始，所以从右边开始比较
     // 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
     while (i < j && array[j] >= key) {
       j--;
     }
     // 当找到比 array[i] 小的时，就把后面的值 array[j] 赋给它
     if (i < j) {
       array[i] = array[j];
     }
     // 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
     while (i < j && array[i] <= key) {
       i++;
     }
     // 当找到比 array[j] 大的时，就把前面的值 array[i] 赋给它
     if (i < j) {
       array[j] = array[i];
     }
   }
   // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
   // 把基准数据赋给正确位置
   array[i] = key;
   return i;
}
 
void quicksort( int array[], int low, int high) {
   // 开始默认基准为 low
   if (low < high) {
     // 分段位置下标
     int standard = getstandard(array, low, high);
     // 递归调用排序
     // 左边排序
     quicksort(array, low, standard - 1);
     // 右边排序
     quicksort(array, standard + 1, high);
   }
}
 
// 合并到一起快速排序
// void quicksort(int array[], int low, int high) {
//   if (low < high) {
//     int i  = low;
//     int j  = high;
//     int key = array[i];
//     while (i < j) {
//       while (i < j && array[j] >= key) {
//         j--;
//       }
//       if (i < j) {
//         array[i] = array[j];
//       }
//       while (i < j && array[i] <= key) {
//         i++;
//       }
//       if (i < j) {
//         array[j] = array[i];
//       }
//     }
//     array[i] = key;
//     quicksort(array, low, i - 1);
//     quicksort(array, i + 1, high);
//   }
// }
 
int main() {
   int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
   int size  = sizeof (array) / sizeof ( int );
 
   // 打印数据
   printf ( "%d \n" , size);
   quicksort(array, 0, size - 1);
   display(array, size);
 
   // int size   = 20;
   // int array[20] = {0};         // 数组初始化
   // for (int i = 0; i < 10; i++) {    // 数组个数
   //   for (int j = 0; j < size; j++) { // 数组大小
   //     array[j] = rand() % 1000;  // 随机生成数大小 0~999
   //   }
   //   printf("原来的数组：");
   //   display(array, size);
   //   quicksort(array, 0, size - 1);
   //   printf("排序后数组：");
   //   display(array, size);
   //   printf("\n");
   // }
 
   return 0;
}

5. 结果展示

（递归调用，不好展示每次排序结果） 。

C/C++实现快速排序算法的思路及原理解析

6. 算法分析

时间复杂度:

  • 最好： o ( n l o g 2 n ) o(n log_{2} n) o(nlog2​n)
  • 最坏： o ( n 2 ) o(n^2) o(n2)
  • 平均： o ( n l o g 2 n ) o(n log_{2} n) o(nlog2​n)

空间复杂度： o ( n l o g 2 n ) o(n log_{2} n) o(nlog2​n) 。

稳定性：不稳定 。

到此这篇关于c/c++实现快速排序算法的思路及原理解析的文章就介绍到这了,更多相关c++实现快速排序算法内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/weixin_42109012/article/details/91645051 。

最后此篇关于C/C++实现快速排序算法的思路及原理解析的文章就讲到这里了,如果你想了解更多关于C/C++实现快速排序算法的思路及原理解析的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

40 4 0
文章推荐： Python异步爬虫多线程与线程池示例详解
文章推荐： Stacs：一款功能强大的静态令牌和凭证扫描安全工具
文章推荐： 深入理解 Go Json.Unmarshal 精度丢失之谜
文章推荐： Python matplotlib可视化绘图详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com