快速排序:是对冒泡排序的一种改进。
先说下快排的一个基本思想:
使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。
就是通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
大喊一声,nb!
一个图:看懂很容易,想出来是真不简单
时间复杂度:
最坏时间复杂度 | |
---|---|
最优时间复杂度 | |
平均时间复杂度 |
代码实现:
/**
* 快速排序算法
*
* @param arr
* 待排序的数组
* @param low
* 排序数组的起始位置
* @param hight
* 排序的结束位置
*/
public static void quickSort_v1(int arr[], int low, int hight) {
if (low < hight) {
// 算出枢轴值
int pivot = partition_v1(arr, low, hight);
// 对小的数组进行递归排序
quickSort_v1(arr, low, pivot - 1);
// 对大的数组进行递归排序
quickSort_v1(arr, pivot + 1, hight);
}
}
/**
* 快速排序的关键算法
*
* @param arr
* 排序的数组
* @param low
* 低位的下标
* @param hight
* 高位的下标
* @return 枢轴的下标索引
*/
public static int partition_v1(int arr[], int low, int hight) {
// 枢轴(就是一个基数而以)
int pivotkey = arr[low];
while (low < hight) {
// 找到不比枢轴元素大的元素位置
while (low < hight && arr[hight] >= pivotkey) {
hight--;
}
// 交换元素位置,使得比枢轴大的元素位置都在右边
swap(arr, low, hight);
// 找到不比枢轴元素小的元素位置
while (low < hight && arr[low] <= pivotkey) {
low++;
}
// 交换元素位置,使得比枢轴小的元素位置都在左边
swap(arr, low, hight);
}
// 返回枢轴元素的下标位置。
return low;
}
// 简单的数组元素位置交换
private static void swap(int[] arr, int low, int hight) {
int t = arr[low];
arr[low] = arr[hight];
arr[hight] = t;
}
对上面代码进行优化:
public static void quickSort_v2(int arr[], int low, int hight) {
if (hight > low) {
while(low < hight) {
// 算出枢轴值
int pivot = partition_v2(arr, low, hight);
/*
* 如果待排序的序列划分的极端不平衡,递归的深度将趋近于n。
* 递归会耗费一定的栈空间,参数越多,耗费的空间也就越多。
* 通过减少递归,缩减堆栈的深度的,来提升整体性能。
*/
// 对小的数组进行递归排序
quickSort_v3(arr, low, pivot - 1);
// 尾递归
low = pivot + 1;
}
}
}
/**
* partition_v1()的改进,优化枢轴选取和减少不必要的交换
* @param arr 待排序的数组
* @param low 低位是下标索引
* @param hight 高位的下标索引
* @return 枢轴的下标位置
*/
private static void quickSortV2(int[] arr, int low, int hight) {
if ((hight - low + 1) > MAX_ARRAY_LENGTH) {
if (hight > low) {
while(low < hight) {
// 算出枢轴值
int pivot = partitionV3(arr, low, hight);
/*
* 如果待排序的序列划分的极端不平衡,递归的深度将趋近于n。
* 递归会耗费一定的栈空间,参数越多,耗费的空间也就越多。
* 通过减少递归,缩减堆栈的深度的,来提升整体性能。
*/
// 对小的数组进行递归排序
quickSortV2(arr, low, pivot - 1);
// 尾递归
low = pivot + 1;
}
} else {
// 当数组(元素个数)很小的时候,快速排序反而不如插入排序了。
binInsertSort(arr, low, hight);
}
}
}