快速排序算法:是排序算法中最常用的算法之一。
复杂度:o(nlog2(n))
思想:随即找某一个位置的值为n,把n放在应该所在的位置index,把数组中小于n的值放在index之前,大于n的值放在index之后。然后对index之前的的数组递归以上逻辑,对index之后的数组递归以上逻辑!
实现思想:从前找到一个大于n的值的位置index1,从后找到一个小于n的值位置index2,交换index1 和 index2 的值,然后考虑把n放到应该所在的位置即可。
本算法是选择最后一个位置的值当做pivot的值。
package cn.horizon.sort;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* 快速排序算法
*
* @author create by [url=xinchunwang@aliyun.com]新春.王[/url] <br>
* date :May 27, 2013 7:47:22 AM
*/
public class QuickSort {
public static void main(String[] args) {
Integer[] arr = initUnSortData(100);
quickSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(Integer[] a) {
quickSort(a, 0, a.length - 1);
}
/**
* 快速排序
*
* @param a 数组a
* @param start 开始位置
* @param end 结束位置
*/
private static void quickSort(Integer[] a, int start, int end) {
int left = start; // 左边界
int right = end - 1; // 右边界
int pivot = a[end]; // 中枢值
while (left < right) {//确保left < right ,退出:left == right
if (a[left] <= pivot) { //如果a[left]< pivot,那么左边界 left++
left++;
continue;
}
if (a[right] > pivot) { //如果 a[right] > pivot ,那么右边界 right --
right--;
continue;
}
/*交换位置。
* 注意:
* left++ : 因为交换后的left 就是 a[right] 对应的值,a[right] 是<= pivot。
* right--:因为 a[right] 对应的值是 a[left] 是> pivot*/
swap(a, left++, right--);
}
//如果left的值 小于 pivot,那么可以确认a[left] 在pivot之前,那么left++,就可以把left++的值和pivot交换了
if (a[left] < pivot) {
left++;
}
swap(a, left, end); //把中枢值放到 left的位置 ,把left现在这个较大的值放到最后面去吧。
if (left - 1 > start) { // pivot 的左侧排序
quickSort(a, start, left - 1);
}
if (left + 1 < end) { // pivot 的右侧排序
quickSort(a, left + 1, end);
}
}
public static void swap(Integer[] a, int left, int right) {
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}
private static Integer[] initUnSortData(int size) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
list.add(new Random(i).nextInt(i + 1));
}
return list.toArray(new Integer[list.size()]);
}
}
分享到:
相关推荐
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
算法-理论基础- 排序- 快速排序(包含源程序).rar
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
详解Java常用排序算法-快速排序
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
基于python的排序算法-快速排序Quick Sort
算法-数据结构和算法-13-快速排序.rar
典型排序算法的c语言实现
归并排序,排序等算法,数据结构,快速排序,链表排序归并排序,排序等算法,数据结构,快速排序,链表排序
算法设计与分析课程,算法实验报告,基于python。涉及快速排序及其改进算法:三路快排。设置"重复率的参数",通过实验可以看到,重复率越高,改进性能越好。
《数据结构与算法》-李春葆 实验报告-典型排序算法实践-快速排序
只需两个时钟即可输出12个数据的排序结果,内容简单易懂
实验内容及要求: 输入n个整数,分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。要求n=10,15,20进行三组排序实验。...实验目的:掌握希尔排序、快速排序、堆排序、归并排序算法。
快速排序算法
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的...
《算法设计与分析》实验报告---快速排序.pdf