java算法面试题:设计一个快速排序。双路快速排…

2018-06-18 03:38:56来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

package com.swift;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class QuickSort {
    /*
     * 快速排序
     */

    public static void main(String[] args) {
        int[] strVoid = new int[] { 11, 66, 22, 0, 55, 2, 0, 11 };
        QuickSort sort = new QuickSort();
        sort.quickSort(strVoid, 0, strVoid.length - 1);
        for (int i = 0; i < strVoid.length; i++) {
            System.out.println(strVoid[i] + " ");
        }
        // 用比较器排序
        List<Integer> list = new ArrayList<Integer>();
        for (Integer i : strVoid) {
            list.add(i);
        }
        Collections.sort(list, new Comparator<Integer>() {

            @Override
            public int compare(Integer arg0, Integer arg1) {
                int num = arg1 - arg0;
                return num;
            }

        });
        for (Integer i : list) {
            System.out.print(i + " | ");
        }
    }

    void quickSort(int[] strDate, int left, int right) {
        int i, j, t, key;
        if (left > right)
            return;

        key = strDate[left]; // temp中存的就是基准数
        i = left;
        j = right;
        while (i != j) {
            // 从后找比key小的或者等的放在key的左边
            while (strDate[j] > key && i < j)
                j--;
            // 从前找比key大的放在key的右边
            while (strDate[i] <= key && i < j)
                i++;
            // 小于就交换位置,等于就停止
            if (i < j) {
                t = strDate[i];
                strDate[i] = strDate[j];
                strDate[j] = t;
            }
        }
        // 两指针相等后,将第一个位置的值与相等处位置的值互换,完成第一轮排序
        strDate[left] = strDate[i];
        strDate[i] = key;

        quickSort(strDate, left, i - 1);// 继续处理左边的,这里是一个递归的过程
        quickSort(strDate, i + 1, right);// 继续处理右边的 ,这里是一个递归的过程
    }
}

这是我的思路,应该属于双路快速排序的一种,快速排序的解决思路太多了,有单路、双路、三路,每种的写法也各有不同,每个人的思路都千奇百怪。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:线程状态、同步

下一篇:elasticsearch6 学习之批量操作