快速排序的效率很高,算法也比较经典。- public class Test3 {
- public static void main(String args[]) {
- int[] lst = getReandArray(20, 100);
- quickSort(lst, 0, lst.length - 1);
- prtArray(lst);
- }
- // 获取指定长度的数组,内部填充int型随机数
- public static int[] getReandArray(int lenght, int max) {
- int[] lst = new int[lenght];
- for (int i = 0; i < lenght; i++)
- lst[i] = (int) (Math.random() * max);
- return lst;
- }
- // 自动输出数组
- public static void prtArray(int[] list) {
- int i = 0;
- while (i < list.length) {
- System.out.print(list[i++] + "\t");
- }
- }
- // 针对array类型的swap
- public static void swap(int[] lst, int x, int y) {
- int temp = lst[x];
- lst[x] = lst[y];
- lst[y] = temp;
- }
- // 实现快排算法
- public static void quickSort(int[] list, int l, int r) {
- int i = l + 1, j = r;
- int key = list[l];
- if (l >= r)
- return;
- while (true) {
- while (list[j] > key)
- j--;
- while (list[i] < key && i < j)
- i++;
- if (i >= j)
- break;
- swap(list, i, j);
- if (list[i] == key)
- j--;
- else
- i++;
- }
- swap(list, l, j);
- if (l < i - 1)
- quickSort(list, l, i - 1);
- if (j + 1 < r)
- quickSort(list, j + 1, r);
- }
- }
复制代码 |
|