欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java算法面试题:设计一个快速排序。双路快速排序,简单易于理解。

程序员文章站 2022-04-08 09:37:42
这是我的思路,应该属于双路快速排序的一种,快速排序的解决思路太多了,有单路、双路、三路,每种的写法也各有不同,每个人的思路都千奇百怪。 ......
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);// 继续处理右边的 ,这里是一个递归的过程
    }
}

java算法面试题:设计一个快速排序。双路快速排序,简单易于理解。

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