type
status
date
slug
summary
tags
category
icon
password
1、快速排序的介绍
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
2、快速排序法示意图

3、快速排序法应用实例
要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序,要求使用快速排序法

4.1、代码实现(按照中间排序)
对 [-9,78,0,23,-567,70]排序成[-9,-567,0,23,78,70]
package com.qf.sort; import java.util.Arrays; public class QuickLySort { public static void main(String[] args) { int[] arr={-9,78,0,23,-567,70}; quick(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quick(int[] arr,int left,int right){ int l=left; int r=right; //取中间值 int mid=arr[(left+right)/2]; int temp=0;//中间值作为交换 //while循环的目的是让mid的左边全是小于mid的 //mid右边的全是大于mid的 while (l<r){ //int[] arr={-9,78,0,23,-567,70}; //第一次换位置 //int[] arr={-9,-567,0,23,78,70}; while (arr[l]<mid){ l=l+1; } while (arr[r]>mid){ r=r-1; } if (l>=r){ break; } temp=arr[l]; arr[l]=arr[r]; arr[r]=temp; if (arr[l]==mid){ r=r-1; } if (arr[r]==mid){ l=l+1; } } if (l==r){ l=l+1; r=r-1; } } }
4.1.1 输出结果

4.2、左递归排序
//左递归排序 if (left<r){ quick(arr,left,r); }
4.2.2 输出结果

4.2、右递归排序
//右递归排序 if (right>l){ quick(arr,l,right); }
4.2.2 输出结果

4.3、代码整合
package com.qf.sort; import java.util.Arrays; public class QuickLySort { public static void main(String[] args) { int[] arr={-9,78,0,23,-567,70}; quick(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quick(int[] arr,int left,int right){ int l=left; int r=right; //取中间值 int mid=arr[(left+right)/2]; int temp=0;//中间值作为交换 //while循环的目的是让mid的左边全是小于mid的 //mid右边的全是大于mid的 while (l<r){ //int[] arr={-9,78,0,23,-567,70}; //第一次换位置 //int[] arr={-9,-567,0,23,78,70}; while (arr[l]<mid){ l=l+1; } while (arr[r]>mid){ r=r-1; } if (l>=r){ break; } temp=arr[l]; arr[l]=arr[r]; arr[r]=temp; //数据相同的时候,移位 if (arr[l]==mid){ r=r-1; } //数据相同的时候,移位 if (arr[r]==mid){ l=l+1; } } //防止栈溢出,相等的情况各自移位 if (l==r){ l=l+1; r=r-1; } //左递归排序 if (left<r){ quick(arr,left,r); } //右递归排序 if (right>l){ quick(arr,l,right); } } }
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。