冒泡排序
冒泡排序从前往后遍历数组，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换两者的位置。
每遍历一轮，最大的元素就会被“冒泡”到最后。
public class Sort {
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 遍历的第 i 轮，需要确定第 arr.length - 1 - i 个元素
for (int j = 0; j < arr.length - 1 - i; j++) {
// 最后 i 个元素已经排好序
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
选择排序
选择排序从前往后遍历数组，每次找到最小的元素，将其放到当前遍历的位置。
public class Sort {
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 遍历的第 i 轮，需要确定第 i 个元素
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 在 i 之后寻找最小的元素
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序
插入排序时，对于一个待排序的序列，从第一个元素开始，依次将每个元素插入到前面已经排好序的序列中，直到所有元素都排好序。
插入时，向前寻找第一个比当前元素小的元素，插入到该元素的后面。
public class Sort {
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 让 0 - i 的元素有序
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
// 向前寻找第一个比当前元素小的元素
swap(arr, j, j - 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
希尔排序
希尔排序是插入排序的改进版，采用分组的方式，将待排序的序列分成若干个子序列，对每个子序列进行插入排序，最后再对整个序列进行一次插入排序。
public class Sort {
public static void shellSort(int[] arr) {
int gap = arr.length / 2;
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j, j - gap);
}
}
gap /= 2;
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
堆排序
堆排序是选择排序的改进版，采用堆的方式，将待排序的序列构建成一个大顶堆或小顶堆，然后依次将堆顶元素取出，放到已排序序列的末尾。
public class Sort {
public static <T extends Comparable<T>> void heapSort(T[] arr) {
int n = arr.length;
// 构建大顶堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次取出堆顶元素
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
public static <T> void heapify(T[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left].compareTo(arr[largest]) > 0) {
largest = left;
}
if (right < n && arr[right].compareTo(arr[largest]) > 0) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
public static <T> void swap(T[] arr, int i, int j) {
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
快速排序
快速排序是分治法的经典应用，采用递归的方式，将待排序的序列分成两个子序列，对每个子序列进行快速排序，最后将两个子序列合并。
public class Sort {
public static <T extends Comparable<T>> void quickSort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static <T> void quickSort(T[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static <T> int partition(T[] arr, int low, int high) {
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j].compareTo(pivot) <= 0) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
public static <T> void swap(T[] arr, int i, int j) {
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
归并排序
归并排序是分治法的经典应用，采用递归的方式，将待排序的序列分成两个子序列，对每个子序列进行归并排序，最后将两个子序列合并。
public class Sort {
public static <T extends Comparable<T>> void mergeSort(T[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
public static <T> void mergeSort(T[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
public static <T> void merge(T[] arr, int low, int mid, int high) {
T[] temp = Arrays.copyOfRange(arr, low, high + 1);
int i = low;
int j = mid + 1;
for (int k = low; k <= high; k++) {
if (i > mid) {
arr[k] = temp[j++];
} else if (j > high) {
arr[k] = temp[i++];
} else if (temp[i].compareTo(temp[j]) <= 0) {
arr[k] = temp[i++];
} else {
arr[k] = temp[j++];
}
}
}
}
基数排序
基数排序是非比较排序的一种，采用分组的方式，将待排序的序列分成若干个子序列，对每个子序列进行计数排序，最后将所有子序列合并。
public class Sort {
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
public static void countingSort(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
}
Comments