快速排序(Quicksort)是对冒泡排序的一种改进。
其主要思路是:
①首先选择一个基准元素,元素可以在待排序序列中随机选取
②把基准元素当做当做一把标尺,对待排序集合进行一遍筛选,使得基准元素左边的元素均小于自身,右边元素均大于自身,由此便将待排序集合分成了两个子区间。
③左右两个子区间分别独立的进行排序,两区间内再选取一个基准元素......以此递归,当左右两边都排好序之后,整个集合也就排好顺序。
实现代码如下
public class QuickSort {//不稳定排序
public void quick(int[] a){
if(a.length>0){
quickSort(a,0,a.length-1);
}
}
/**
* 快速排序
* @param a
*/
private void quickSort(int[] a,int low,int high) {
if(low<high){
int middle = getMiddle(a,low,high);//找基准元素
quickSort(a,0,middle-1);//递归,排列基准元素左边的子区间
quickSort(a,middle+1,high);//递归,排列基准元素右边的子区间
}
}
/**
* 获取基准元素的下标
* @param a
* @param low
* @param high
* @return
*/
private int getMiddle(int[] a, int low, int high) {
int tep = a[low];//基准元素
while (low<high){
while (low<high&&a[high]>=tep){
high--;
}
a[low] = a[high];
while (low<high&&a[low]<=tep){
low++;
}
a[high] = a[low];
}
a[low] = tep;//插入到排序后正确的位置
return low;
}
//测试代码!
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] a= {12,1,52,63,26,49,-1,59,100,-2,29,87,55,63,77};
quickSort.quick(a);
for (int num:a) {
System.out.println(" "+num);
}
}
}
运行结果
TIM截图20191110200926.png