概述
目录
一、冒泡排序（Bubble Sort）
二、快速排序（Quick Sort）
引言
快速排序算法
算法描述
将区间按照基准值划分为左右两半部分的常见方式：
1、Hoare版
2、挖坑法
3、前后指针法
快速排序的优化
规模较小时的优化
三数取中法
非递归实现快速排序
快速排序总结
一、冒泡排序（Bubble Sort）
冒泡排序的原理
从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
- 以从小到大排序为例，
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。
什么时候最快
当输入的数据已经是正序时（都已经是正序了，我还需要你冒泡排序吗？）
什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢？）
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
时间复杂度：O(n^2)
空间复杂度：O(1)
代码
public static void bubbleSort(int[] array){
for(int i=0; i< array.length-1 ;i++){
for(int j = 0; j < array.length-1-i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
}优化：避免已经有序的情况下无意义的循环判断
public static void bubbleSort2(int[] array){
for(int i=0; i< array.length-1 ;i++){
boolean flg = false ;
for(int j = 0; j < array.length-1-i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if(!flg){
break;
}
}
}二、快速排序（Quick Sort）
引言
终于我们的高手要登场了，这个被列为20世纪十大算法之一的快速排序，前面我们介绍的希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的时间，将关键字较大的记录从前面直接移到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数
快速排序算法
快速排序的基本思想是：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式：
1、Hoare版
Hoare法是以快排的创始人Hoare命名的，也是快排最初的实现版本。其基本思想就是用两个指针分别指向待排序数组的开头和结尾。
- 如果我们取头值作为我们的key值，那么我们一定要让右指针先移动
- 如果我们取尾值作为我们的key值，那么我们一定要让左指针先移动
如图，我们取头值为key值
怎样移动and如何找基准
- right指针直到找到小于key的值才停下来
- left指针直到找到大于key的值才停下来
- 将left和right所对应的值进行交换。重复上述过程直到两者相遇
- 相遇后，将key下标的值与相遇处的值交换
- 此时相遇处就是基准
下面用动图演绎一下
代码：
//Hoare法
public static int partitionHoare(int[] array,int low,int high){
int key = low;
while(low < high){
while (low < high && array[high] >= array[key]){
high--;
}
//此时high下标就是要找的数字
while (low < high && array[low] <= array[key]){
low++;
}
//此时low下标就是要找的数字
swap(array,low,high); //low和high下标的元素交换
}
//此时low和high相遇了
swap(array,low,key);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}需要注意的是
2.挖坑法
我们需要在key处挖一个坑（把6拿出来存在一个tmp变量里），形成一个坑位，然后R向左找比6小的放进坑里，就又形成了一个新的坑，然后L向右找，找到比6大的，放进新的坑
我们还是用动图演绎
挖坑法的好处是更容易我们理解，我们根据这个思路写一个用挖坑法的快排
//挖坑法
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}3、前后指针法
版本1
顾名思义，需要两个指针，一个在前一个在后，分别用cur表示前指针，prev表示后指针，初始时，我们规定cur在prev的后一个位置，这里我们还是选择第一个数为基准值
- prev每次都需要指向从左到它本身之间最后一个小于基准值的数
- 如果cur的值大于基准值，这时只让cur++
- 如果cur指向的位置小于基准值
- 这时我们让prev++
- 判断prev++后是否与cur的位置相等
- 若不相等，则交换cur和prev的值
- 直到cur > R后，我们再交换prev和key，这样基准值的位置也就确定了
下面我们依旧是动图演绎
代码
//前后指针法1
private static int partition(int[] array,int low,int high){
int prev = low;
int cur = low+1;
while (cur <= high){
if(array[cur] < array[low] && array[++prev]!=array[cur]){
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,low);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
版本2
这个写法可能更好理解，但实质是一样的
//前后指针法2
private static int partition2(int[] array,int low,int high){
int d = low+1;
int tmp = array[low];
for(int i = low+1;i <= high; i++){
if(array[i] < tmp){
swap(array,i,d);
d++;
}
}
swap(array,d-1,low);
return d-1;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition2(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}快速排序的优化
规模较小时的优化
每次递归的时候，数据都是再慢慢变成有序的
当数据量少且趋于有序的时候，我们可以直接使用插入排序进行优化
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
if(right-left+1 <= 10000){ //某个区间内的小规模排序直接插入排序
//进行插入排序
insertSortRange(array,left,right);
return;
}
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
public static void insertSortRange(int[] array,int low, int end){
for(int i = low+1 ; i<=end ;i++){
int tmp = array[i];
int j = i-1;
for(; j >= low ; j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}但是这个优化并没有根本解决 有序情况下 递归深度太深的优化
如果想根本上解决问题，就得尽量让每次划分更均匀
三数取中法
我们用 三数取中法 选key
- 三数取中：头，尾，中间元素中 大小居中 的那一个
再把这个元素和队头元素互换，作为key
我们来看一下的代码
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
//三数取中，找到首，中，尾三个数中 中等大小的数的下标
private static int medianOfThreeIndex(int[] array, int left, int right){
int mid = left + ((right-left)>>>1);
//int mid = (right+left)/2 ;
if(array[left] < array[right]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
if(array[mid] < array[right]){
return right;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
//1.某个区间内的小规模排序直接插入排序【优化的是区间内的比较】
if(right-left+1 <= 10000){
//进行插入排序
insertSortRange(array,left,right);
return;
}
//2.三数取中法【优化的是本身的分割】
int index = medianOfThreeIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}非递归实现快速排序
我们需要用到栈
我们之前是在已经确定基准点之后，对剩余的区间递归进行同样的操作
我们现在创建一个栈，把剩余区间的左、右位置的下标分别放入栈中，如图是已经找到一个基准6的情况
然后弹出栈顶一个元素9给H，再弹出一个栈顶元素6给L，根据新的L和H找到新的基准，再重复上面的操作
代码
//挖坑法
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
//快速排序（非递归）
public static void quickSortNor(int[] array,int left,int right){
Stack<Integer> stack = new Stack<>();
int pivot = partitionHole(array,left,right);
if(pivot > left+1){
//说明左边有两个或两个以上数据
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1){
stack.push(pivot+1);
stack.push(right);
}
while (!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot = partitionHole(array,left,right);
if(pivot > left+1){
//说明左边有两个或两个以上数据
stack.push(left);
stack.push(pivot-1);
}
if(pivot < right-1){
stack.push(pivot+1);
stack.push(right);
}
}
}
快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
最后
以上就是能干帅哥为你收集整理的【八大排序③】快速排序（动图演绎Hoare法、挖坑法、前后指针法）一、冒泡排序（Bubble Sort）二、快速排序（Quick Sort）的全部内容，希望文章能够帮你解决【八大排序③】快速排序（动图演绎Hoare法、挖坑法、前后指针法）一、冒泡排序（Bubble Sort）二、快速排序（Quick Sort）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复