算法之快速排序
2023-09-27 14:27:45 时间
快速排序 是1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称为分治法 (Divide-and-Conquer Method)。
分治法的基本思想 :
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的基本思想 :
设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
(1) 分解
在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1]和R[pivotpos+1..high],并使 左边子区间中所有记录的关键字均<=基准记录的关键字pivot.key,右边的子区间中所有记录的关键字均>=pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
(2) 求解
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]分别进行快速排序。
(3) 组合
因为当“求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,“组合”步骤无须做什么,可看做是空操作。
1 #include <stdio.h> 2 3 int partition(int *a, int low, int high) 4 { 5 int key = a[low]; 6 while(low<high) 7 { 8 while(low<high && a[high]>key) 9 high--; 10 if(a[high]<key) 11 a[low] = a[high]; 12 while(low<high && a[low]<=key) 13 low++; 14 if(a[low]>key) 15 a[high] = a[low]; 16 } 17 a[low] = key; 18 return low; 19 } 20 void quick_sort(int a[], int low, int high) 21 { 22 int pos; 23 if(low<high) 24 { 25 pos = partition(a, low, high); 26 quick_sort(a, low, pos-1); 27 quick_sort(a, pos+1, high); 28 } 29 } 30 31 int main() 32 { 33 int i; 34 int arr[] = {12, 33, 25,87, 90, 77, 35, 77, 46, 29}; 35 quick_sort(arr,0, 9); 36 for(i=0;i<10;i++) 37 { 38 printf("%d\t", arr[i]); 39 } 40 printf("\n"); 41 return 0; 42 }
相关文章
- 算法之--快速排序
- Unity图片优化神器 - Dither算法进阶方案
- 排序算法之归并排序
- 快速排序算法介绍
- RRT算法的仿真
- C#,数值计算,矩阵的行列式(Determinant)、伴随矩阵(Adjoint)与逆矩阵(Inverse)的算法与源代码
- C#,双向链表(Doubly Linked List)快速排序(Quick Sort)算法与源代码
- [算法]快速排序,归并排序,堆排序的数组和单链表实现
- 排序算法系列之(零)——排序初体验
- 【排序算法】快速排序的详解
- 快速排序算法
- 排序算法及分析(插入、希尔、选择、冒泡)
- 看动画学算法之:排序-快速排序
- C/C++_排序算法
- C语言-函数指针-快速排序算法
- 动画+原理+代码,解读十大经典排序算法
- 八大排序算法总结
- 32排序算法之快速排序
- 算法-排序算法
- 24数据结构与算法分析之---二叉树的概念