<>一、高级排序

<>【1】希尔排序
public class 希尔排序 { public static void main(String[] args) { Integer[] arr =
{3, 1, 5, 2, 4, 4, 9, 8, 7}; Hill.sort(arr);
System.out.println(Arrays.toString(arr)); } } class Hill { public static void
sort(Integer[] t) { Integer temp; Integer h = 1; while (h < (t.length / 2)) { h
= h * 2 + 1; } while (h != 0) { for (int i = h; i < t.length; i++) { for (int j
= i; j >= h; j -= h) { if (t[j] < t[j - h]) { temp = t[j]; t[j] = t[j - h]; t[j
- h] = temp; } else { break; } } } h /= 2; } } }
<>【2】归并排序
public class 归并排序 { public static void main(String[] args) { Integer[] arr =
{3, 1, 5, 2, 4, 4, 9, 8, 7}; Merge.sort(arr);
System.out.println(Arrays.toString(arr)); } } class Merge { private static
Integer[] buffer; static void sort(Integer[] t) { buffer = new
Integer[t.length]; split(t, 0, t.length - 1); } private static void
split(Integer[] integers, Integer startIndex, Integer stopIndex) { if
(startIndex == stopIndex) { return; } Integer midIndex = (stopIndex +
startIndex) / 2; split(integers, startIndex, midIndex); split(integers,
midIndex + 1, stopIndex); sortByMerge(integers, startIndex, midIndex,
stopIndex); } private static void sortByMerge(Integer[] integers, Integer l,
Integer m, Integer r) { Integer bufferIndex = l; Integer leftIndex = l; Integer
rightIndex = m + 1; while (leftIndex <= m && rightIndex <= r) { if
(integers[leftIndex] < integers[rightIndex]) { buffer[bufferIndex++] =
integers[leftIndex++]; } else { buffer[bufferIndex++] = integers[rightIndex++];
} } while (leftIndex <= m) { buffer[bufferIndex++] = integers[leftIndex++]; }
while (rightIndex <= r) { buffer[bufferIndex++] = integers[rightIndex++]; } if
(r + 1 - l >= 0) System.arraycopy(buffer, l, integers, l, r + 1 - l); } }
<>【3】快速排序
public class 快速排序 { public static void main(String[] args) { Integer[] arr =
{3, 1, 5, 2, 4, 4, 9, 8, 7}; Quick.sort(arr, 0, arr.length - 1); //
Quick.partition(arr,1,arr.length - 1);
System.out.println(Arrays.toString(arr)); } } class Quick { public static void
sort(Integer[] arr, Integer leftIndex, Integer rightIndex) { if (leftIndex >=
rightIndex) { return; } Integer partitionIndex = partition(arr, leftIndex,
rightIndex); sort(arr, leftIndex, partitionIndex - 1); sort(arr, partitionIndex
+ 1, rightIndex); } static Integer left; static Integer right; static Integer
key; static Integer temp; public static Integer partition(Integer[] arr,
Integer l, Integer r) { left = l; right = r + 1; key = l; while (true) { while
(arr[key] < arr[--right]) { if (right <= left) { break; } } while (arr[key] >
arr[++left]) { if (right <= left) { break; } } if (left < right) { temp =
arr[left]; arr[left] = arr[right]; arr[right] = temp; } else { temp = arr[key];
arr[key] = arr[right]; arr[right] = temp; break; } } return right; } }