快速排序Quick sort(转)
2024-09-02 05:30:56
原理,通过一趟扫描将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
举个例子
如无序数组[6 2 4 1 5 9]
a),先把第一项[6]取出来,
用[6]依次与其余项进行比较,
如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边
如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~
一趟排完后变成下边这样:
排序前 6 2 4 1 5 9
排序后 2 4 1 5 6 9
b),对前半拉[2 4 1 5]继续进行快速排序
重复步骤a)后变成下边这样:
排序前 2 4 1 5
排序后 1 2 4 5
前半拉排序完成,总的排序也完成:
排序前:[6 2 4 1 5 9]
排序后:[1 2 4 5 6 9]
排序结束
以下代码实现仅供参考
static int partition(int[] unsorted, int low, int high)
{
int pivot = unsorted[low];
while (low < high)
{
while (low < high && unsorted[high] > pivot) high--;
unsorted[low] = unsorted[high];
while (low < high && unsorted[low] <= pivot) low++;
unsorted[high] = unsorted[low];
}
unsorted[low] = pivot;
return low;
} static void quick_sort(int[] unsorted, int low, int high)
{
int loc = ;
if (low < high)
{
loc = partition(unsorted, low, high);
quick_sort(unsorted, low, loc - );
quick_sort(unsorted, loc + , high);
}
} static void Main(string[] args)
{
int[] x = { , , , , , };
quick_sort(x, , x.Length - );
foreach (var item in x)
{
Console.WriteLine(item + ",");
}
Console.ReadLine();
}
原文转自 http://www.cnblogs.com/kkun/archive/2011/11/23/quick_sort.html#3418166
最新文章
- mac os 下搭建android开发环境
- json,pickle
- Java BigDecimal 加减乘除运算
- chrome控制台支持多行js模式
- 克隆或拷贝的VMware虚拟机IP问题解决
- GL10控制图形旋转
- Android学习笔记02
- 【机器学习算法-python实现】Adaboost的实现(1)-单层决策树(decision stump)
- window.getSelection和document.selection
- triplet loss 在深度学习中主要应用在什么地方?有什么明显的优势?
- vue路由对不同界面进行传参及跳转的总结
- BZOJ5419[Noi2018]情报中心——线段树合并+虚树+树形DP
- 【BZOJ4543】Hotel加强版(长链剖分)
- Ubuntu常用操作命令
- Centos7 Firewall 防火墙配置应用实例参考(转)
- webstorm 设置 sass自动编译问题
- java 反射机制--根据属性名获取属性值
- ASP.NET MVC 富文本Ueditor编辑 后台传值前端乱码解决方案
- 国内比特币bitcoin交易平台
- uestc 1072 a ^ b