1、算法概念。
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
2、算法思想。
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3、实现思路。
①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,…,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
②把左区作为一个整体,用①的步骤进行处理,右区进行相同的处理。(即递归)
③重复第①、②步,直到左区处理完毕。
Java实现代码:
/**
* description : 快速排序
* @autor kwzhang
* modify :2012-6-20
*
* @param pData
* @param left
* @param right
* @return
*/
static void quicksort(int n[], int left, int right) {
int dp;
if (left < right) {
dp = partition(n, left, right);
quicksort(n, left, dp - 1);
quicksort(n, dp + 1, right);
}
}
static int partition(int n[], int left, int right) {
int pivot = n[left];
while (left < right) {
while (left < right && n[right] >= pivot)
right--;
if (left < right)
n[left++] = n[right];
while (left < right && n[left] <= pivot)
left++;
if (left < right)
n[right--] = n[left];
}
n[left] = pivot;
return left;
}
分享到:
相关推荐
算法设计与分析 一PRESETATION 仅做参考,请勿copy冲查重塔峰 排序算法性能分析 ...但注意理论上快速排序的空间复杂度较高为O(n),且最坏情况时时间复杂度也达到了O(n2)。所以快速算法也较为常用。
1、熟悉快速排序的串行算法 2、熟悉快速排序的并行算法 3、实现快速排序的并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速...
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
知道快速排序算法的思想,但是一直都没有动手写,今天写了下,发现还不是那么容易
舞动的排序算法 快速排序 通过动画演示快速排序,很好的学习,课程资源。
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
快速排序算法C语言实现,快排序算法QuickSort.cpp
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 ...# sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据
快速排序算法快速排序算法快速排序算法快速排序算法快速排序算法
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
c语言版本的数据结构的快速排序算法,适用于新手学习
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
详细解释了快速排序的java实现.里面有代码,还有注释说明
C++排序算法之快速排序源码
自己编写的基于java的快速排序和归并算法
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例) 快速排序算法(C经典实例)
呵呵,传上来供大家学习使用~8种排序算法 包括:选择排序 冒泡排序 快速排序 等~~