快速排序(quick sort) C ~
本文共 1999 字，大约阅读时间需要 6 分钟。
快速排序性能好坏主要在于主元的选取。
下面 有两种选主元的方式:
(1) : 每次选取当前序列的第一个元素
(2):选取选取当前序列的 首元素、 中间元素 、 尾元素 的 中位数.
核心 ： 每次 给主元找到准确的排序位置（效率高的原因也就在于每次找的的都是准确的位置）。
(1) 选取首元素为基准（主元）的实现：
#includeint a[101];void sort(int a[], int left, int right) { int i, j; int tmp; if(left > right) return ; tmp = a[left]; i = left; j = right; int t; while(i != j){ while(a[j] >= tmp && i < j) j--; while(a[i] <= tmp && i < j) i++; t = a[j]; a[j] = a[i]; a[i] = t; } a[left] = a[j]; a[j] = tmp; sort(a, left, j-1); sort(a, j+1, right); }void quick_sort(int a[], int n) { sort(a, 0, n-1); } int main() { int n, i; scanf("%d",&n); for(i = 0; i < n; i++ ){ scanf("%d",&a[i]); } quick_sort(a, n); for(i = 0; i < n; i++ ){ printf("%d ", a[i]); } return 0; }
（2）选取中位数为基准数据的实现:
#include#define MAX 100void swap(int *a, int *b) { int tmp; tmp = *a; *a = *b; *b = tmp; }int get_pivot(int a[], int left, int right) //选 主元 就是把 left, right , mid 按照从小到大排序 并把 中间值 返回当做主元 { int mid = (left + right)/2; if(a[left] > a[mid]) swap(&a[left], &a[mid]); if(a[left] > a[right]) swap(&a[left], &a[right]); if(a[mid] > a[right]) swap(&a[mid], &a[right]); swap(&a[left], &a[mid]); return a[left]; } void sort(int a[], int left, int right) { if(left > right) //不能少 return ; int pivot = get_pivot(a, left, right); int i, j; i = left; j = right; while(i != j){ while(a[j] >= pivot && i < j)//主语 这两个while语句的顺序 很重要 不能调换 j--; while(a[i] <= pivot && i < j)// 主元选取在left 则每次必须是从right端 开始 查询 也就是 j先-- 找合适的 i++; //然后在i++ (位置不可调换) if(i < j) swap(&a[i], &a[j]); } //出来时一定是 i == j swap(&a[j], &a[left]); //找到 主元的合适位置 sort(a, left, j-1);//递归 处理左半边 sort(a, j+1, right);//递归处理右半边 return ; } void quick_sort(int a[], int n)//提供 优雅的 接口 { sort(a, 0, n-1); } int main() { int a[MAX]; int n, i; scanf("%d",&n); for(i = 0; i < n ; i++ ){ scanf("%d",&a[i]); } quick_sort(a, n); for(i = 0; i < n; i++ ){ printf("%d ",a[i]); } return 0; }
你可能感兴趣的文章
STM32开源代码——光敏传感器
查看>>
STM32开源代码——UART串口程序
查看>>
个人项目——STM32接入机智云教程
查看>>
STemWin学习笔记——字体
查看>>
STemWin学习笔记——XBF格式字体显示
查看>>
STemWin学习笔记——TTF格式字体显示
查看>>
STemWIn学习笔记——汉字显示（外部存储器）
查看>>
Python学习笔记——Python提高-2
查看>>
Python学习笔记——多任务-进程
查看>>
Python学习笔记——多任务-线程
查看>>
Vim学习笔记——前言
查看>>
Vim学习笔记——小试牛刀
查看>>
Vim学习笔记——帮助
查看>>
Python学习笔记——网络通信过程
查看>>
Python学习笔记——正则表达式
查看>>
Python学习笔记——数据结构与算法
查看>>
Python学习笔记——顺序表
查看>>
Python学习笔记——链表
查看>>
MarkDown学习笔记——语法
查看>>
Python学习笔记——栈和队列
查看>>