快速排序算法的学习快速排序算法的学习

思路快速排序是采用分治的思路
【快速排序算法的学习】1. 从数组中选中一个元素a，遍历数组
2. 把比a大的元素交换a后面，比a小的元素交换到a前面
3. 交换结束后，可以把数组分成两部分，a前面的（<=a）和a后面的(>=a)
4. 分别将这两部分排好序后，数组也就有序了
5. 对两部分还是进行一样的操作，选中元素a，交换，分割。
6. 就是不停的交换后分割数组，一直到分割后的部分都只有一个元素，无法再交换，整个数组有序
实现错误代码
使用递归的方式实现分割下面是关于我根据这个思路后写出来第一版（错误）的快速排序，其中有两个bug需要修复

文章图片

文章图片

public static void quickSort(int[] arr,int left,int right){ // 被分割到只剩下一个元素了 if (left >= right) { return; }// 选了第一个元素 int pivot = left; while (left < right){ /* left>=right时退出循环说明此时的left == right == pivot pivot已经满足了将数组分成两部分的条件 */ while (arr[right] >= arr[pivot]){ right--; } // 交换之后pivot要变，left和right只改变值，下标依旧遍历数组 if(right > pivot){ swap(arr,right,pivot); pivot = right; }while (arr[left] <= arr[pivot]){ left++; } if (left < pivot) { swap(arr,left,pivot); pivot = left; } } // 使用递归的方式进行分割 quickSort(arr,0,pivot-1); quickSort(arr,pivot+1,arr.length-1); }

View Code 在代码中这两行没有考虑到数组越界的问题

while (arr[right] >= arr[pivot]){ right--; } while (arr[left] <= arr[pivot]){ left++; }

最后的递归代码没有确定边界，当被分割的两部分进行排序时会互相干扰

quickSort(arr,0,pivot-1); quickSort(arr,pivot+1,arr.length-1);

不完全实现
将这两个bug修复后的代码，算是完成了算法的实现。

文章图片

public static void quickSort(int[] arr,int left,int right){ // 被分割到只剩下一个元素了 if (left >= right) { return; }// 保存开始和结束下标 int start = left , end = right; // 选了第一个元素 int pivot = left; while (left < right){ /* left>=j时退出循环说明此时的i == right == pivot pivot已经满足了将数组分成两部分的条件 */ // 交换之后pivot要变，i和j依旧遍历数组 while (right > pivot && arr[right] >= arr[pivot]){ // 在后面的元素并且比pivot小 right--; } if(arr[right] < arr[pivot]){swap(arr,right,pivot); pivot = right; }while (left < pivot && arr[left] <= arr[pivot]){ left++; } if (arr[left] > arr[pivot]) { swap(arr,left,pivot); pivot = left; } } // 使用递归的方式进行分割 quickSort(arr,start,pivot-1); quickSort(arr,pivot+1,end); }

View Code
但是还有很多可以优化的地方。

在循环中有left和right两个分别和pivot交换的地方，可以进一步优化
- 可以将两次交换过程，简化成一个三方交换
- 再使用一个循环外的临时变量保存值，将交换变成单向赋值过程
pivot选的是数组的第一个元素，在极端情况下会导致时间复杂度高
- 如果数组原本是倒序的，要将数组变成正序的，快速排序的分割数组阶段完全不生效，总过程类似冒泡排序
- pivot可以取left和right中间的一个随机值

正经实现
首先是pivot获取从left到right之间的随机值的方法

// 在区间中获取一个随机值 public static int getRandom(int upperBound,int lowerBound){ return new Random().nextInt(upperBound - lowerBound + 1) + lowerBound; }

然后是两次交换简化成一个三方交换的过程，思路如下：

原本先交换的是right和pivot，然后交换left和pivot，但是不改变left和right这两个下标值，而pivot需要改变
所以 pivot跟left交换时，其实用的是从right那里换来的值
相当于arr[right]变成arr[pivot],arr[left] 变成arr[right],arr[pivot] 变成 arr[left]

所以交换的代码变成这样

文章图片

while (left < right){while (right > pivot && arr[right] >= arr[pivot]){ right--; }while (left < right && arr[left] <= arr[pivot]){ left++; } if(pivot == left && pivot == right){ continue; } /* 将两次交换变成三方交换首先交换的是right和pivot，然后交换left和pivot，但是不改变left和right这两个下标值，而pivot需要改变所以交换过程是(如果没有交换，有left==right==pivot，也成立) 也就是arr[right]<-->arr[pivot]再arr[left]<-> arr[pivot] 相当于 arr[right] ->arr[pivot], arr[left] -> arr[right], arr[pivot] -> arr[left] */ int tmp = arr[pivot]; arr[pivot] = arr[right]; arr[right] = arr[left]; arr[left] = tmp; pivot = left; }

View Code
再通过保存一个变量value 将这个三方交换简化成单向赋值
然后完整的快速排序算法如下

1public static void quick_sort(int[] arr,int left,int right){ 2if (left >= right) { 3return; 4} 5 6// 保存开始和结束下标 7int start = left , end = right; 8 9//使用一个在i和j之间的随机数字 10int pivot = getRandom(right,left); 11// 保存pivot下标对应的值 12int value = https://www.it610.com/article/arr[pivot]; 13 14/* 15使用left和right两个指针， 16首先移动right指针，遇到小于pivot的就进行交换， 17然后移到left指针，遇到大于pivot的就进行交换， 18实现大的元素放到它后面，小的元素放到它前面 19*/ 20 21while (left < right){ 22/* 23值使用value比较 24下标使用pivot比较 25所以不需要更新pivot下标在数组的值 26只要在循环外面赋值即可 27*/ 28while (right> pivot && arr[right] >= value){ 29// 在后面的元素并且比pivot大 30right--; 31} 32while (left < right && arr[left] <= value){ 33left++; 34} 35if(pivot == left && pivot == right){ 36continue; 37} 38/* 39pivot的值通过交换变成left， 40但是暂时不改变arr[left]，因为（如果有）下一次交换会让它赋值为arr[right]，并不需要它本身的值 41*/ 42arr[pivot] = arr[right]; 43arr[right] = arr[left]; 44pivot = left; 45} 46arr[pivot] = value; 47 48quick_sort(arr,start,pivot-1); 49quick_sort(arr,pivot+1,end); 50}

在leetcode上用第912题排序数组试了下正确性，时间复杂度确实有一点点减少