大佬教程收集整理的这篇文章主要介绍了【数据结构与算法】快速排序(三种代码实现以及工程优化),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
快速排序是一种分治的排序算法。它将一个数组分成两个子数组,将两个部分独立地排序。递归调用发生在处理整个数组之后。
快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式。
[ 比基准值小的数] 基准值 [ 比基准值大的数]
public static void main(String[] args) {
int[] arr = {2, 2, 2, 0, 0, 0, 1};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int pivot = arr[low]; //切分元素,设定基准值为从左向右第一个元素的下标
while (i <= j) {
if (arr[i] <= pivot) //扫描元素小于基准值,左指针右移
i++;
else {
swap(arr, i, j); //扫描元素大于基准值,两个指针的元素交换,右指针左移。使该元素到基准值右侧(确定i所指向元素属于大于区域,那就把它放到大于区域)
j--;
}
} //j最后所指向的位置是小于区域的最后一个元素
swap(arr, low, j); //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
双向扫描的思路是,头尾指针往中间扫描,从左找到大于主元的元素,从右找到小于等于主元的元素二者交换,继续扫描,直到左侧无大元素,右侧无小元素
public static void main(String[] args) {
int[] arr = {1,5,6,3,2,1,4,5,2};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr,int low,int high){
int i = low + 1, j = high; //左右扫描指针
int pivot = arr[low]; //切分元素,设定基准值为从左向右第一个元素
while(i<=j){
while(i<=j&&arr[i]<=pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
i++;
while(i<=j&&arr[j]>pivot) //扫描元素大于基准值,右指针左移(注意保证i<=j)
j--;
if(i<j) //注意该处判断
swap(arr,i,j); //左右指针指向元素交换
}
swap(arr,low,j); //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static void swap(int[] arr,int a,int b){
int tmp = arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
双向扫描的思路是,多考虑相等的情况,i 指针从左向右扫描,j 指针从右向左扫描,e永远指向相等区域的第一个元素(小于区域的后面第一个元素)。
public static void main(String[] args) {
int[] arr = {5,2,1,3,6,7};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void quickSort(int[] arr,int low,int high){
if(arr==null||arr.length<2||low>=high) return;
int []j = partition(arr,low,high); //返回两个坐标
quickSort(arr,low,j[0]-1); //将左半部分arr[low...j[0]-1]排序
quickSort(arr,j[1]+1,high); //将右半部分arr[j[0]+1...high]排序
}
private static int[] partition(int[] arr,int low,int high){
int i = low+1;
int j = high;
int pivot = arr[low];
int e = low+1;
while(i<=j){
if(arr[i]<pivot){ //小于pivot,i位置和e位置交换,e++,i++
swap(arr,i,E);
e++;
i++;
}
else if(arr[i]==pivot){ //等于pivot,i++
i++;
}else{
swap(arr,i,j); //大于pivot,s位置和j位置交换,j--
j--;
}
}
swap(arr,low,e-1); //将基准值插入到相应位置
return new int[]{e,j}; //返回等于区域左边第一个元素下标和等于区域右边最后一个元素下标。
}
private static void swap(int[] arr,int a,int b){
int tmp = arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
分析一下上面的双向扫描分区法,在定义pivot时都指定第一个元素为pivot的值,有可能pivot的值不在数组中居中,有可能退化成O(n^2)时间复杂度。
举个极端情况的例子:
每次选取pivot都为首元素,而pivot的值恰好为最大元素,则pivot最后需要到最右的位置,那么下一次递归调用右半部分arr[j+1...high]就没有了,只有左半部分arr[low...j-1]。而不巧下一次递归pivot选取第一个元素又是最大的,又要重复以上步骤。
数据规模类似从n 到n-1 到n-2 ……到1 ,做n层,最后时间复杂度是O(n^2)级,然而理想的时间复杂度是O(nlogn)级别。
理想情况:
如果每次pivot恰好是中间大小元素,那每次数据规模都变为n/2。写出时间复杂度的递推式: T(n) = 2T(n/2)+O(n) (O(n)是遍历数组的复杂度,T(n/2)是递归一个分支的复杂度)
利用Master公式:
T(N) = a*T(N/b) + O(N^d)
其中 a >= 1 and b > 1 是常量,其表示的意义是n表示问题的规模,a表示递归的次数也就是生成的子问题数,b表示每次递归是原来的1/b之一个规模,O(N^d)表示分解和合并等其他操作所要花费的时间复杂度。 使用前提是递归子问题规模相同。
可以得到,a=2,b=2,d=1,log(b,a)=d,复杂度为O(N^d * logN)也就是O(nlogn)
所以我们要做的就是尽力让pivot每次都能选到数组中间大小元素位置。
在low,high,midIndex(low和high的中间元素下标)之间,选一个中间大小值作为主元。
优化一下双向扫描分区法的patition函数:
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int midIndex = low + ((high - low) >> 2); //中间下标
int midValueIndex = -1; //中值的下标
if ((arr[low] <= arr[midIndex] && arr[high] >= arr[midIndex]) || (arr[low] >= arr[midIndex] && arr[high] <= arr[midIndex]))
midValueIndex = midIndex;
else if ((arr[high] <= arr[low] && arr[midIndex] >= arr[low]) || (arr[high] >= arr[low] && arr[midIndex] <= arr[low]))
midValueIndex = low;
else midValueIndex = high;
swap(arr,low,midValueIndeX); //交换中间大小值和low位的值,让pivot依然位于low的位置,但其值变为中间大小值
int pivot = arr[low]; //切分元素,设定基准值为从左向右第一个元素
while (i <= j) {
while (i <= j && arr[i] <= pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
i++;
while (i <= j && arr[j] > pivot) //扫描元素大于基准值,右指针左移(注意保证i<=j)
j--;
if (i < j) //注意该处判断
swap(arr, i, j); //左右指针指向元素交换
}
swap(arr, low, j); //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
三点中值法使用比较广。java中使用三点中值法。
保证pivot是数组的绝对中值 但会使复杂度的的常数因子扩大,有可能得不偿失。
把数组按照每五个元素为一组分组,使用插入排序选出每组中的中值,再把这些中值放到一个数组中使用插入排序选出中值也就是pivot,将其与low的值做交换,保证程序剩下部分正常运行。
private static void quickSort(int[] arr, int low, int high) {
if (arr == null || arr.length < 2 || high <= low) return;
int j = partition(arr, low, high); //切分
quickSort(arr, low, j - 1); //将左半部分arr[low...j-1]排序
quickSort(arr, j + 1, high); //将右半部分arr[j+1...high]排序
}
private static int partition(int[] arr, int low, int high) {
int i = low + 1, j = high; //左右扫描指针
int midValueIndex = getMedian(arr, low, high);
swap(arr,midValueIndex,low);
int pivot = arr[low];
while (i <= j) {
while (i <= j && arr[i] <= pivot) //扫描元素小于基准值,左指针右移(注意保证i<=j)
i++;
while (i <= j && arr[j] > pivot) //扫描元素大于基准值,右指针左移(注意保证i<=j)
j--;
if (i < j) //注意该处判断
swap(arr, i, j); //左右指针指向元素交换
}
swap(arr, low, j); //将基准值插入到相应位置,也就是把基准值和小于区域的最后一个元素交换。使得基准值右侧就是大于区域
return j;
}
private static int getMedian(int[] arr, int p, int r) { //获取中值方法
int size = r - p + 1; //数组长度
//每五个元素一组
int groupSize = (size % 5 == 0) ? (size / 5) : (size / 5 + 1);
//存储各小组中值
int medians[] = new int[groupSize];
int indexOfMedians = 0;
//对每一组进行插入排序
for (int j = 0; j < groupSize; j++) {
//单独处理最后一组,因为最后一组可能不满5个元素
if (j == groupSize - 1) {
InsertionSort(arr, p + j * 5, r); //排序最后一组
medians[indexOfMedians++] = arr[(p + j * 5 + r) / 2]; //最后一组的中间那个
} else {
InsertionSort(arr, p + j * 5, p + j * 5 + 4); //排序非最后一个组的某个组
medians[indexOfMedians++] = arr[p + j * 5 + 2]; //当前组(排序后)的中间那个
}
}
InsertionSort(medians, 0, medians.length - 1);
return medians[medians.length / 2];
}
private static void InsertionSort(int[] arr,int begin,int end){ //插入排序
if(arr==null||arr.length<2) return; //去除无效情况
for(int i = begin+1; i < end; i++){
for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--)
swap(arr,j,j+1);
}
}
private static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
用的较少,看需求。
插入排序的真实复杂度是n(n-1)/2,快速排序的真实复杂度是n(logn+1) 估计一下:
public static void quickSort(int[] A, int p, int r) {
if (p < r) {
//待排序个数小于等于8的时候,插入排序
if (p - r + 1 <= 8) {
InsertionSort(A, p, r); //插入排序
} else { //快排
int q = partition2(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
}
以上是大佬教程为你收集整理的【数据结构与算法】快速排序(三种代码实现以及工程优化)全部内容,希望文章能够帮你解决【数据结构与算法】快速排序(三种代码实现以及工程优化)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。