最近在看一些面试题,发现很多面试过程中都会要求手写快速排序,查阅一些博客发现别人写的并不是特别清楚而且也很难记住,所以为了更好的掌握这个算法,所以在这篇文章中,将自己的学习过程记录下来,你将学习到快速排序算法和使用 Java 如何实现快速排序。
快速排序是一种基于分而治之的排序算法,其中:
1、通过从数组中选择一个中心元素将数组划分成两个子数组,在划分数组时,将比中心元素小的元素放在左子数组,将比中心元素大的元素放在右子数组。
2、左子数组和右子数组也使用相同的方法进行划分,这个过程一直持续到每个子数组都包含一个元素为止。
3、最后,将元素组合在一起以形成排序的数组。
中心元素(pivot element):有的地方翻译为:枢轴元素、基元,基准元素,我这里就叫做中心元素
选择不同位置的中心元素,快速排序就有不同的变体,比如可以选择:第一个元素、最后一个元素以及左端、右端和中心位置上的三个元素的中值作为中心元素,在这里,我们将选择数组的最后一个元素作为中心元素。
现在重新排列数组,将比中心元素小的放在左边,比中心元素大的放在右边。
重新排列数组的方法如下:
1、指针固定在中心元素上,将中心元素与从第一个索引开始的元素进行比较。
2、如果该元素大于中心元素,则为该元素设置第二指针。
3、现在将中心元素与其他元素进行比较,如果到达的元素小于中心元素,则将较小的元素和上次找到的较大元素交换位置。
4、同样,重复该过程以将下一个更大的元素设置为第二指针,并且将其和另一个较小的元素交换位置。
5、该过程一直进行到到达倒数第二个元素为止。
6、最后将中心元素与第二个指针指向的元素交换位置。
再次分别为左子部分和右子部分选择了中心元素,并且重复步骤2,子数组被分割,直到每个子数组只有一个元素,至此,该数组已经通过快速排序算法升序排好序了。
可以借助以下插图了解快速排序算法的工作原理。
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
Java 实现快速排序的代码如下:
public class QuickSort {
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针,首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素,将比中心元素大的放在右边,比中心元素小的放在左边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 将比中心元素小的元素和指针指向的元素交换位置
// 如果第一个元素比中心元素小,这里就是自己和自己交换位置,指针和索引都向下一位移动
// 如果元素比中心元素大,索引向下移动,指针指向这个较大的元素,直到找到比中心元素小的元素,并交换位置,指针向下移动
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
// 将中心元素和指针指向的元素交换位置
int temp = array[pointer ];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 获取划分子数组的位置
int position = partition(array, low, high);
// 左子数组递归调用
quickSort(array, low, position -1);
// 右子数组递归调用
quickSort(array, position + 1, high);
}
}
public static void main(String[] args) {
int[] array = {6,72,113,11,23};
quickSort(array, 0, array.length -1);
System.out.println("排序后的结果");
System.out.println(Arrays.toString(array));
}
}
排序过程的结果如下:
[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 72, 113, 11, 23]
[6, 11, 113, 72, 23]
[6, 11, 23, 72, 113]
[6, 11, 23, 72, 113]
排序后的结果
[6, 11, 23, 72, 113]
从这个排序结果我们可以知道整个排序过程。
时间复杂度 | O表示 |
---|---|
最好 | O(n * log n) |
最差 | O(n * n) |
平均 | O(n * log n) |
空间复杂度 | O(log n) |
稳定性 | 不稳定 |
平均复杂度[Big-O] :
在不出现上述条件时发生。
快速排序的空间复杂度为O(log n)。
在以下情况下使用Quicksort算法
Dreamweaver设计的纯文字网页太单调了,想要添加漂亮的星空背景,该怎么添加呢?...
一些场景,比如canvas获取的图片,或者微信开发sdk返回的图片格式是data:img格式...
CSS display 属性 注释:如果规定了 !DOCTYPE,则 Internet Explorer 8 (以及更...
1.核心功能 此组件功能包含: 图片裁剪(裁剪框拖动,裁剪框改变大小); 图片马...
在很多项目中,配置文件是不可缺少的,一般配置文件会用变量或者数组进行设置,...
纯css图切换 练习 教程来自snwebsite 1 2 3 [Ctrl+A 全选 注: 引入外部Js需再刷...
各位小伙伴们好,今天我们来聊一聊JavaScript 中的“类型系统”。 但是在开始之...
序 本文主要研究一下tunny的workerWrapper workerWrapper type workerWrapper st...
复制代码 代码如下: li {width:300px; height:23px; line-height:24px:} ul li行...
问题来源 这个问题,源于上传图片文件的时候,后台限制了2MB的大小,but在调起相...