排序算法-交换排序-快速排序详解

快速排序:

总的来说就是先找一个基数(一般以low作为基准数) 把比基准数大的放在基准数的右边比基数小的放在左边然后再对其左右进行排序

栗子:

以数组arr[] = { 2, 3, 8, 7, 1} 为栗子

首先要有两个指针 low 和high 以及基准数 在此以arr[low]作为基准数把比它大的放在它右边比它小的数放在它左边  temp 保存一下基准数的值 因为排序过程中它的值会被覆盖

然后先让 high指针左移 如果大于等于基准数则 high–  否则放在基准数前边

也就是赋值给low所在位置  arr[low] = arr[high]

为什么要这么赋值?

以此例子来说 元素1 应该呆的位置就是a[0] 动态的low和high就是基准数的左边和右边 当不满足右边的时候要放左边当不满足左边的时候要放右边最终low和high碰头就是基准数的位置

low位置值被修改了开始移动 low  让low指针右移 如果小于等于基准数则 low++  否则放在基准数后边

此时low位置值 大于基准数应该放后边 也就是赋值给high所在位置  arr[high] = arr[low]

high位置的值被修改了 开始移动 high  让high指针左移如果大于等于基准数则 high–  否则放在基准数前边

然后再对基准数左边和右边进行排序即可 也就是{1} 和{8,7,3} 循环此过程即可 自己推导下

下一次结果应是

此时并没有完还有对 {3,7} 进行排序 才是真正的完成

过程可能有点复杂,多拿几组数组自己试一试不过代码很简答

算法代码:

package test1;

import java.util.*;

public class Demo {
    public static void main(String[] args) {
        int arr[] = { 2, 3, 8, 7, 1};
        quickSort(arr,0,arr.length-1);
    }

    private static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            int index = getIndex(arr,low,high);
//			分别对基准数的左边和右边进行排序
            quickSort(arr,low,index-1);
            quickSort(arr,index+1,high);

        }
    }

    private static int getIndex(int[] arr, int low, int high) {
        int temp = arr[low];
        while(low < high) {
//			先让high和 基准数进行比较如果 arr[high] >=temp 说明 arr[high]就在基准数后边
            while(low < high && arr[high] >=temp) {
                high--;
            }
//			此时arr[high] 值小于基准数 应该放基准数前边 也就是low这个位置 你总不能说随便放吧
//			所以快排才有了 low high 两个指针
            arr[low] =arr[high];
//			然后让 low和 基准数进行比较如果 arr[low] <=temp 说明 arr[low]就在基准数左边
            while(low < high && arr[low] <=temp) {
                low++;
            }
//			此时arr[low] 值大于基准数 应该放基准数右边 也就是high这个位置
            arr[high]= arr[low];

        }
//		当low
        arr[low] =temp;
        System.out.println(Arrays.toString(arr));
        return low;
    }

}

 

输出结果:

© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发