快速排序的原理就是以递归的方式进行划分
划分：从数组中选择一个数作为枢纽，将数组划分成两部分，一部分小于枢纽，一部分大于枢纽
这里列举三种快速排序，第一种是基本的快速排序。第二种优化枢纽选择方式，第三种优化长度较小数组的排序为插入排序。
一、选择最右为中枢的快速排序
步骤：
1，选择最右一个为枢纽。
2，划分整个数组。数组变成：[比枢纽小，...，枢纽，比枢纽大，...]
3，比枢纽小的部分递归1,2。
4，比枢纽大的部分递归1,2。
public static int[] data = {3,7,8,0,9,5,4,1,6,2};
/**
* 交换位置
* @param i
* @param j
*/
private static void swap(int i, int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
/**
* 递归
* @param leftIndex
* @param rightIndex
*/
private static void recursion(int leftIndex, int rightIndex){
if(leftIndex >= rightIndex){
return;
}else{
int pivot = data[rightIndex]; //以最右一个为枢纽
int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
}
}
/**
*
* 划分
* 以最右一个为枢纽，对“最左” 到“最右-1”进行划分；
* 最终划分成两份，左份小于枢纽，右份大于枢纽，枢纽在中间
* @param leftIndex
* @param rightIndex
* @param pivot 枢纽
* @return 枢纽索引
*/
private static int partition(int leftIndex, int rightIndex, int pivot){
/** 要划分区是leftIndex到rightIndex - 1。 */
int left = leftIndex - 1; //要划分区域最左-1
int right = rightIndex; //要划分区域最右+1
while(true){
while(data[++left] < pivot); //从最左往右遍历，找到一个大的
while(right > 0 && data[--right] > pivot); //从最右往左遍历，找到一个小的
if(left >= right){
break;
}else{
swap(left, right);
}
}
swap(left, rightIndex);//枢纽归位
return left;
}
public static void main(String[] args) {
recursion(0, data.length - 1);
System.out.println(Arrays.toString(data));
}
二、三数据项取中为中枢的快速排序
这种快速排序优化了中枢的选取，但是同时失去了对长度<=3的数组快速排序的能力
步骤：
1，对数组的三个值：第一个值(first)、最后一个值(last)、中间一个值(center)，在对应的三个位置上排序，选中间一个为枢纽；最后枢纽和"最后-1"交换位置（即，将枢纽放在倒数第二个位置），数组变成：[三个较小......，枢纽，三个较大......]
2.1，<=3，手动排序
2.2，>3，划分整个数组。数组变成：[三个较小，比枢纽小......，枢纽，比枢纽大......，三个较大]
3，比枢纽小的部分递归1,2。
4，比枢纽大的部分1,2。
public static int[] data = {3,7,8,0,9,5,4,1,6,2};
/**
* 交换位置
* @param i
* @param j
*/
private static void swap(int i, int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
/**
* 由于长度小于等于3无法进行快速排序。
* 当长度小于等于3时直接手动排序，推出递归
* 对<=3的数组手动排序
* @param left
* @param right
*/
private static void manualSort(int left, int right){
int size = right - left + 1;
if(size <= 1){
return;
}
if(size == 2){
if(data[left] > data[right]){
swap(left, right);
}
}else{
if(data[left] > data[right - 1]){
swap(left, right - 1);
}
if(data[left] > data[right]){
swap(left, right);
}
if(data[right - 1] > data[right]){
swap(right - 1, right);
}
}
}
/**
* 选择枢纽
* @param left
* @param right
* @return
*/
private static int medianOf3(int left, int right){
/** 从数组的开始，结束，和中间，对着在对应的三个位置上排序，枢纽放在right-1处，并返回枢纽 */
int center = (right + left) / 2;
if(data[left] > data[center]){
swap(left, center);
}
if(data[left] > data[right]){
swap(left, right);
}
if(data[center] > data[right]){
swap(center, right);
}
/** 最后把居中的那个放在right-1处，作为枢纽 */
swap(center, right - 1);//
return data[right - 1];
}
/**
*
* 划分
* @param leftIndex
* @param rightIndex
* @param pivot
* @return
*/
private static int partition(int leftIndex, int rightIndex, int pivot){
/**
* leftIndex经过medianOf3已经是小的了
* rightIndex经过medianOf3已经是大的了
* rightIndex - 1 是枢纽
* 要划分的区域是leftIndex+1到rightIndex-2。
*/
int left = leftIndex; //要划分区域最左-1
int right = rightIndex - 1; //要划分区域最右+1
while(true){
while(data[++left] < pivot); //从最左往右遍历，找到一个大的
while(data[--right] > pivot); //从最右往左遍历，找到一个小的
if(left >= right){
break;
}else{
swap(left, right);
}
}
swap(left, rightIndex - 1);//枢纽归位
return left; //返回枢纽位置
}
/**
* 递归
* @param leftIndex
* @param rightIndex
*/
private static void recursion(int leftIndex, int rightIndex){
if(rightIndex - leftIndex + 1 <= 3){
manualSort(leftIndex, rightIndex);//手动排序
}else{
int pivot = medianOf3(leftIndex, rightIndex);//选择枢纽
int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
}
}
public static void main(String[] args) {
recursion(0, data.length - 1);
System.out.println(Arrays.toString(data));
}
三、较小数组改用插入排序的快速排序
将二中的手动排序改成插入排序，条件改成<10
public static int[] data = {3,7,8,0,9,5,4,1,6,2};
/**
* 交换位置
* @param i
* @param j
*/
private static void swap(int i, int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
/**
* 选择枢纽
* @param left
* @param right
* @return
*/
private static int medianOf3(int left, int right){
/** 从数组的开始，结束，和中间，对着在对应的三个位置上排序，枢纽放在right-1处，并返回枢纽 */
int center = (right + left) / 2;
if(data[left] > data[center]){
swap(left, center);
}
if(data[left] > data[right]){
swap(left, right);
}
if(data[center] > data[right]){
swap(center, right);
}
/** 最后把居中的那个放在right-1处，作为枢纽 */
swap(center, right - 1);//
return data[right - 1];
}
/**
* 插入排序
* @param left
* @param right
*/
private static void insertionSort(int left, int right){
for(int i = left+1; i <= right; i++){
int temp = data[i];
int j = i - 1;
while(j >= left && data[j] >= temp){
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
/**
*
* 划分
* @param leftIndex
* @param rightIndex
* @param pivot
* @return
*/
private static int partition(int leftIndex, int rightIndex, int pivot){
/**
* leftIndex经过medianOf3已经是小的了
* rightIndex经过medianOf3已经是大的了
* rightIndex - 1 是枢纽
* 要划分的区域是leftIndex+1到rightIndex-2。
*/
int left = leftIndex; //要划分区域最左-1
int right = rightIndex - 1; //要划分区域最右+1
while(true){
while(data[++left] < pivot); //从最左往右遍历，找到一个大的
while(data[--right] > pivot); //从最右往左遍历，找到一个小的
if(left >= right){
break;
}else{
swap(left, right);
}
}
swap(left, rightIndex - 1);//枢纽归位
return left; //返回枢纽位置
}
/**
* 递归
* @param leftIndex
* @param rightIndex
*/
private static void recursion(int leftIndex, int rightIndex){
if(rightIndex - leftIndex + 1 < 10){
insertionSort(leftIndex, rightIndex);//插入排序
}else{
int pivot = medianOf3(leftIndex, rightIndex);//选择枢纽
int pivotIndex = partition(leftIndex, rightIndex, pivot);//以pivot为枢纽进行划分两份，pivotIndex是最终枢纽的位置
recursion(leftIndex, pivotIndex - 1); //左侧再次递归划分
recursion(pivotIndex + 1, rightIndex);//右侧再次递归划分
}
}
public static void main(String[] args) {
recursion(0, data.length - 1);
System.out.println(Arrays.toString(data));
}
相关推荐
快速排序快速排序 快速排序 快速排序 快速排序 快速排序
本主题将深入探讨四种常见的排序算法：堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先，让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法，利用了数据...
4. **快速排序（Quick Sort）**： 快速排序是由C.A.R. Hoare提出的，是目前最常用的排序算法之一。它采用分治策略，选取一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。平均...
全面的排序算法实现，包括插入排序、合并排序、堆排序、快速排序。 堆排序：HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序：InSertion_Sort 讲解详见...
（1） 完成5种常用内部排序算法的演示，5种排序算法为：快速排序，直接插入排序，选择排序，堆排序，希尔排序； （2） 待排序元素为整数，排序序列存储在数据文件中，要求排序元素不少于30个； （3） 演示程序开始，...
数据结构（c语言版）严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法，它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点，适用场景不同，下面将逐一详细介绍，并结合...
以下是关于"冒泡排序，选择排序，插入排序，希尔排序，堆排序，归并排序，快速排序"这七种常见排序算法的源码实现及相关知识点的详细解释： 1. **冒泡排序**：冒泡排序是一种简单的排序算法，它重复地遍历待排序的...
选择排序、插入排序、冒泡排序以及快速排序和归并排序的Ｃ语言实现，绝对可用
本文将深入探讨Java编程语言中实现的七种主要排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及归并排序。每种算法都有其独特性，适用于不同的场景和数据特性。 1. **直接插入排序**：...
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
4. **快速排序**： 快速排序是C++中最常用的排序算法之一，由英国计算机科学家C.A.R. Hoare提出。它使用分治策略，选择一个基准元素，将数组分为两部分，一部分的所有元素都小于基准，另一部分的元素都大于基准，...
快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码快速排序源码 快速排序源码
冒泡排序和快速排序的时间性能 冒泡排序和快速排序是两种常用的排序算法，它们的时间性能是开发者和研究人员所关心的热点话题。在本文中，我们将对冒泡排序和快速排序的时间性能进行深入分析和比较。 冒泡排序是一...
本主题涵盖了六种经典的排序算法：希尔排序、堆排序、快速排序、简单选择排序、插入排序和冒泡排序。这些算法各有特点，适用于不同的场景，下面将逐一详细介绍。 1. **希尔排序**：希尔排序是由Donald Shell提出的...
4. **实现难度**：快速排序的实现相对简单，而合并排序需要更复杂的合并过程。 在实际应用中，根据具体需求选择合适的排序算法至关重要。例如，在数据库系统中，可能需要考虑稳定性；在在线服务中，可能更关心响应...
选择排序、插入排序和快速排序都是经典的排序算法，各有其特点和适用场景。接下来，我们将详细探讨这三个排序算法。 1. **选择排序（Selection Sort）** 选择排序是一种简单直观的排序算法。它的基本思想是在未...
在本文中，我们将深入探讨四种常见的内部排序方法：插入排序、快速排序、选择排序以及再次提到的选择排序。这四种排序方法在不同的场景下各有优劣，理解它们的工作原理和性能特性对于优化算法至关重要。 **1. 插入...
排序算法java版，速度排行：冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht