小胡博客

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

平均复杂度 : nlog2n 最坏时间复杂度 : n^2 最好时间复杂度 : nlog2n 空间复杂度: log2n 稳定性: 不稳

代码：

package com.xiaohu.suanfa.sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 小胡哥哥
 * NO BB show your code
 * 快速排序，原理:
 * 选择一个基点key和一个最小的值low和一个最大的值heigh,key比low小，放左边，比heigh大，放右边
 * 之后使用递归
 */
public class QuickSort {
    public static void main(String[] args) {
        print();
    }

    private static int[] getArray() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一串数字，以,为 间隔");
        String str = sc.nextLine();
        //以,切割获得数组
        String[] strArray = str.split(",");
        int[] arr = new int[strArray.length];
        for (int i = 0; i < strArray.length; i++) {
            //将原先的字符串数组转换为数字数组
            arr[i] = Integer.parseInt(strArray[i]);
        }
        return arr;
    }

    private static void print() {
        int[] array = getArray();
        System.out.println("排序之前的数组:" + Arrays.toString(array));
        long startTime = System.currentTimeMillis();
        int[] sort = sort(array, 0, array.length - 1);
        long endTime = System.currentTimeMillis();
        System.out.println("排序之后的数组:" + Arrays.toString(sort));
        System.out.println("总共花费:" + (endTime - startTime) + "毫秒");
    }

    private static int[] sort(int[] arr, int low, int high) {
        //i是小值，j是大值

        int key = 0;
        int i = low;
        int j = high;
        if (i < j) {
            key = arr[i];
            //设定key在最左边
            while (i < j) {

                while (key <= arr[j] && i < j) {
                    j--;
                }
                //跳出循环则代表，key的值大于右边的值,进行位置替换
                arr[i] = arr[j];
                while (key >= arr[i] && i < j) {
                    i++;
                }
                arr[j] = arr[i];
            }
            //不满足 i<j的话 则代表key已经找到自己正确的位置
            arr[i] = key;
            //进行递归调用,找到了key的正确位置，则可以进行二分查找
            sort(arr, low, i - 1);
            sort(arr, i + 1, high);
        }

        return arr;
    }
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦