数据结构与算法——快速排序
程序员文章站
2022-07-09 12:39:28
...
/**
*
* 1.在待排序的元素任取一个元素作为基准(通常选第一个元素,但最的选择方法是从待排序元素中随机选取一个作为基准),称为基准元素;
* 2.将待排序的元素进行分区,比基准元素大的元素放在它的右边,比其小的放在它的左边;
* 3.对左右两个分区重复以上步骤直到所有元素都是有序的。
* 快速排序是一种不稳定的算法
* 快速排序的时间复杂度是O(n2)
* @param arr--待排序数组
* @param start--数组的左边界
* @param end--数组的右边界
* @author zzc
* @date 2019.3.14
*
*/
public static void quickSort(int[] arr,int start,int end){
//递归过程中,当左边界比有边界小的时候,进行排序
if(start<end){
//定义一个基准数,一般选择为第一个数
int stard = arr[start];
//定义左右两个哨兵
int low = start;
int high = end;
//第一层循环代表一趟遍历过程,直到两个哨兵重合,则退出循环
while (low<high) {
//右边哨兵先动,向左一个一个寻找比基准数小的数
while (low<high && stard<=arr[high]) {
high--;
}
//找到了一个比基准数小的数,就把右边哨兵对应的数字赋值给左边哨兵对应的数字
arr[low] = arr[high];
//左边哨兵再动,向右一个一个寻找比基准数大的数
while (low<high && arr[low]<stard) {
low++;
}
//找到了一个比基准数大的数,就把左边哨兵对应的数字赋值给左边哨兵对应的数字
//我称这一过程为拆东墙补西墙
arr[high] = arr[low];
}
//当左右哨兵重合时,把基准数赋值给左边哨兵所在的数值,当然赋值给右边的也行
arr[low] = stard;
//递归调用
quickSort(arr,start,low);
quickSort(arr,low+1,end);
}
}
public static void main(String[] args) {
int array[] = {10,5,3,1,7,2,8};
System.out.println("排序之前");
for(int element : array){
System.out.print(element+" ");
}
quickSort(array,0,array.length-1);
System.out.println("/n排序之后");
for(int element : array){
System.out.print(element+" ");
}
}
上一篇: 二叉树的遍历、查找、节点删除
下一篇: 攻防世界 Crypto进阶 简单的rsa