【学习笔记】

改进版快速排序

昨天手撕了原始快速排序的基本算法，一直在思考这些基础算法的使用场景，今天分享一个改进版的快速排序算法，用于对数字进行快速部分排序，举个例子：从10万个无序的数里面选出最小的10个并有序输出。适合用到以下改进版快速排序的思想：

Talk is cheap，show the code~

package sort;import org.junit.Test;/*** 改进版快速排序* @author jsyuger* 该类为原始快速排序算法的改进版实现，提高快速排序的效率。* 使用场景：快速整理部分排序* 举个例子：在10万个无序的数字里面挑选最小的前10个数,并有序输出*/
public class MoreQuickSort {//快速排序的入口public void quickStart(int []arr) {int low = 0 ; int high = arr.length -1 ;quickSort(arr , low , high);}//快速排序的递归实现public void quickSort(int []arr ,int low , int high) {if(low == high)  return ; //终止条件int i = low ; int j = high ;int key = 0 ; //递归分割点//快速排序，从小到大while(low<high) {while(i<j && arr[i] <= arr[j]) j-- ;if(i<j && arr[i] > arr[j]) swapper(arr ,i ,j);while(i<j && arr[i] <= arr[j]) i++ ;if(i<j && arr[i] > arr[j]) swapper(arr ,i ,j);if(i == j) { //进入递归key = i ;if(key >= 9)  quickSort(arr , low ,key); //当key>=9，只需对key前面的分区进行排序。else {quickSort(arr , key+1 , high);quickSort(arr , low , key);}break ;}}}private void swapper(int[] arr, int i, int j) {// 数组交换两个元素的位置int temp = arr[i] ;arr[i] = arr[j] ;arr[j] = temp ; }@Testpublic void quickTest() {int[] arr = {6 , 9 , 0 , 3 , 1 , 90 , 8 , 4 , 76 ,51 ,89 ,72 ,8 ,12 ,23 ,43 ,66 ,91 ,81 ,71 ,22 ,33 ,88};for(int i : arr) System.out.print(" " + i); //排序前System.out.print("\n");quickStart(arr);		for(int i : arr) System.out.print(" " + i); //排序后数组现状System.out.print("\n最小的前10个数字是：");for(int i = 0 ;i<=9 ;i++) System.out.print(" " + arr[i]); //排序后最小的前10个数字}}

输出结果：

以上算法实现，暂用一个数组模拟代替10万个数（正常情况下通过文件读取），可以发现排序后的数组仅仅只对前10个数进行了有序排序，从第11个数字开始基本是无序的，也就是说后面的数没有一直进行快速排序，改进版的快速排序时间复杂度是远低于O(nlogn)的，大大提高了原始快排的效率。