1.选定一个位置 2.这个位置的左边都要比这个位置的数字小，这个位置的右边都要大于这个位置 3.以同样的方式处理左半部分 4.以同样的方式处理右半部分
public static void quickSort(int[] array, int begin, int end) {
if (end <= begin) return;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
static int partition(int[] a, int begin, int end) {
// pivot: 标杆位置，counter: 小于pivot的元素的个数
int pivot = end, counter = begin;
for (int i = begin; i < end; i++) {
if (a[i] < a[pivot]) {
int temp = a[counter]; a[counter] = a[i];
a[i] = temp;
counter++;
}
}
int temp = a[pivot];
a[pivot] = a[counter];
a[counter] = temp;
return counter;
}1.将目标分为二 2.左边及右边各自有序后，合并左右 3.每个部分都重复1，2的步骤
public static void mergeSort(int[] array, int left, int right) {
if (right <= left) return;
int mid = (left + right) >> 1;
// (left + right) / 2
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
// 中间数组
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
// 也可以用 System.arraycopy(a, start1, b, start2, length)
}- 建立堆
- 将堆顶元素移到这一轮的最后
- 重复1，2
static void heapify(int[] array, int length, int i) {
int left = 2 * i + 1, right = 2 * i + 2;
int largest = i;
if (left < length && array[left] > array[largest]) {
largest = left;
}
if (right < length && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
heapify(array, length, largest);
}
}
public static void heapSort(int[] array) {
if (array.length == 0)
return;
int length = array.length;
for (int i = length / 2-1; i >= 0; i-)
heapify(array, length, i);
for (int i = length - 1; i >= 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}