快速排序
程序员文章站
2022-03-02 08:10:35
...
分析:升序为例,以数组第一个数为key,把小于它的数交换到左边,大于它的数交换到右边。
public class Test09 {
//快速排序
public static void quickSort(int[] arr, int start, int end) {
int key = arr[start];
int keyIndex = start;
int oldStart = start;
int oldEnd = end;
while (start < end) {
while (start < end) {
if (key > arr[end]) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
keyIndex = end;
break;
}
end--;
}
while (start < end) {
if (key < arr[start]) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
end--;
keyIndex = start;
break;
}
start++;
}
}
if (oldStart < keyIndex - 1) {
quickSort(arr, oldStart, keyIndex - 1);
}
if (keyIndex + 1 < oldEnd) {
quickSort(arr, keyIndex + 1, oldEnd);
}
}
public static void main(String[] args) {
int[] arr = {45, 1, 50, 34, 90, 60, 34};
printArray(arr, "排序前");
quickSort(arr, 0, arr.length - 1);
printArray(arr, "排序后");
}
public static void printArray(int[] arr, String message) {
System.out.print(message);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}