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