排序
冒泡排序
package class01;
import java.util.Arrays;
public class Code02_BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//每次确定一个最值元素
for (int e = arr.length - 1; e > 0; e--) { // 0 ~ e
for (int i = 0; i < e; i++) {
//从0开始，如果相邻元素小则交换位置，一轮进行完毕后，会确定一个最值元素
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
// 交换arr的i和j位置上的值
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}选择排序
最终得到1，2，9，8，3，6
package class01;
import java.util.Arrays;
public class Code01_SelectionSort {
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) { // i ~ N-1
int minIndex = i;//记录此轮最小元素的值
for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
插入排序
package class01;
public class Code03_InsertionSort {
public static void insertionSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
//0~0有序的
//0~i想有序
for(int i = 1;i < arr.length;i++) {
for(int j = i - 1;j >= 0 && arr[j] > arr[j+1];j--) {
swap(arr,j,j+1);
}
}
}
public static void swap(int[] arr,int i,int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
int[] num = {12,3,2,56,23};
insertionSort(num);
for(int i : num) {
System.out.print(i+" ");
}
}
}快速排序
package class02;
import java.util.Arrays;
public class Code06_QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
// arr[l..r]排好序
public static void quickSort(int[] arr, int L, int R) {
if (L < R) {
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1); // < 区
quickSort(arr, p[1] + 1, R); // > 区
}
}
// 这是一个处理arr[l..r]的函数
// 默认以arr[r]做划分，arr[r] -> p <p ==p >p
// 返回等于区域(左边界，右边界), 所以返回一个长度为2的数组res, res[0] res[1]
public static int[] partition(int[] arr, int L, int R) {
int less = L - 1; // <区右边界
int more = R; // >区左边界
while (L < more) { // L表示当前数的位置 arr[R] -> 划分值
if (arr[L] < arr[R]) { // 当前数 < 划分值
swap(arr, ++less, L++);
} else if (arr[L] > arr[R]) { // 当前数 > 划分值
swap(arr, --more, L);
} else {
L++;
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
归并排序
package class02;
import java.util.Arrays;
public class Code01_MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R) {//当有一个指针越界循环就跳出
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];//将较小的元素拷贝至辅助数组，然后两个指针都右移一步
}
//另一个指针可能还没有跳出，此时需要将剩余的元素拷贝至辅助数组
while (p1 <= M) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
//最后将辅助数组中的内容拷贝回原数组
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
}
堆排序
package class02;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Code03_HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) { // O(N)
heapInsert(arr, i); // O(logN)
}
// for(int i = arr.length -1; i >=0; i--) {
// heapify(arr, i, arr.length);
// }
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) { // O(N)
heapify(arr, 0, heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
// 某个数现在处在index位置，往上继续移动
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// 某个数在index位置，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1; // 左孩子的下标
while (left < heapSize) { // 下方还有孩子的时候
// 两个孩子中，谁的值大，把下标给largest
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 父和较大的孩子之间，谁的值大，把下标给largest
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
