最近溫習了一下之前學的七七八八的常見排序算法
快速排序
// 快速排序 時間復雜度O(nlogn) 穩(wěn)定性:不穩(wěn)定
public static int[] quickSort(int[] nums, int start, int end) {
if (start < end) {
int i = start;
int j = end;
int temp = nums[start]; // 基準值 (優(yōu)化點 可先取mid位子處的元素和start位子互換再開始快排)
while (i < j) {
while (i < j && nums[j] > temp) {
j--;
}
if (i < j)
nums[i++] = nums[j];
while (i < j && nums[i] < temp) {
i++;
}
if (i < j) {
nums[j--] = nums[i];
}
}
nums[i] = temp;
quickSort(nums, start, i - 1);
quickSort(nums, i + 1, end);
}
return nums;
}
歸并排序
// 歸并排序 時間復雜度O(nlogn) 穩(wěn)定性: 穩(wěn)定
public static void mergeSort(int[] nums, int i, int j) {
if (i < j) {
int mid = i + ((j - i) >> 1);
mergeSort(nums, i, mid);
mergeSort(nums, mid + 1, j);
merge(nums, i, mid, j);
}
}
private static void merge(int[] nums, int i, int mid, int j) {
int[] arr = new int[j - i + 1];
int x = i;
int y = mid + 1;
for (int a = 0; a < arr.length; a++) {
if (x > mid) {
arr[a] = nums[y++];
} else if (y > j) {
arr[a] = nums[x++];
} else if (nums[x] <= nums[y]) {
arr[a] = nums[x++];
} else
arr[a] = nums[y++];
}
for (int b = 0; b < arr.length; b++) {
nums[i + b] = arr[b];
}
}
插入排序
// 插入排序 時間復雜度 O(n^2) 穩(wěn)定性:穩(wěn)定
public static void insertSort(int[] nums) {
// 思路是 在已有序 序列基礎上 繼續(xù)添加元素 // 即在第一個元素后 遍歷要添加的元素
// 從右到左依次比較有序序列 將要添加的元素插入合適的位子
for (int i = 1; i < nums.length; i++) {
int target = nums[i];
int pre = i - 1;
while (pre >= 0 && nums[pre] > target) {
nums[pre + 1] = nums[pre];
pre--;
}
nums[pre + 1] = target;
}
}
希爾排序
// 希爾排序是對插入排序的更高效的優(yōu)化 插入排序即為gap為1的特殊場景 時間復雜度 O(nlog^2 n) 穩(wěn)定性不穩(wěn)定
//由于多次插入排序葱淳，我們知道一次插入排序是穩(wěn)定的钝腺，不會改變相同元 素的相對順序，
// 但在不同的插入排序過程中蛙紫，相同的元素可能在各自的插入排序中移動拍屑，最后其穩(wěn)定性就會被打亂；
public static void shellSort(int[] nums) {
int length = nums.length;
for (int gap = length >> 1; gap > 0; gap = gap >> 1) {
for (int i = gap; i < length; i++) {
insertSortByGap(nums, gap, i);
}
}
}
private static void insertSortByGap(int[] nums, int gap, int i) {
int current = nums[i];
int pre = i - gap;
while (pre >= 0 && nums[pre] > current) {
nums[pre + gap] = nums[pre];
pre -= gap;
}
nums[pre + gap] = current;
}
堆排序
// 借助優(yōu)先隊列 (堆)進行排序 時間復雜度O(nlogn) 穩(wěn)定性 不穩(wěn)定
public static void heapSort(int[] nums) {
PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length);
for (int i = 0; i < nums.length; i++) {
queue.offer(nums[i]);
}
for (int i = 0; i < nums.length; i++) {
nums[i] = queue.poll();
}
}
位圖排序
// 位圖排序 利用底層1字節(jié)8個bit位 來進行0,1設置
// 使用場景為:內(nèi)存限制較大,數(shù)據(jù)不重復,知道數(shù)組中的最大值
public static int[] bitSort(int[] nums, int max) {
BitSet bitSet = new BitSet(max + 1);
for (int i = 0; i < nums.length; i++) {
bitSet.set(nums[i]);
}
return bitSet.stream().toArray();
}
冒泡排序
// 冒泡排序 時間復雜度度O(n^2) 穩(wěn)定性:穩(wěn)定
public static void bubbleSort(int[] nums) {
for (int i = nums.length - 1; i > 0; i--) {
boolean isSwap = true;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
isSwap = false;
}
if (isSwap)
break;
}
}
選擇排序
// 選擇排序 時間復雜度度O(n^2) 穩(wěn)定性:不穩(wěn)定
public static void selectSort(int[] nums) {
for (int i = nums.length - 1; i > 0; i--) {
int maxIndex = i;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[maxIndex]) {
maxIndex = j;
}
}
if (i != maxIndex)
swap(nums, i, maxIndex);
}
}
計數(shù)排序
// 計數(shù)排序 時間復雜度: 當輸入的元素是 n 個 0到 k 之間的整數(shù)時坑傅，時間復雜度是O(n+k)
public static void countingSort(int[] nums, int max) {
int[] counting = new int[max + 1];
for (int i = 0; i < nums.length; i++) {
counting[nums[i]] += 1;
}
int x = 0;
for (int i = 0; i < counting.length; i++) {
if (counting[i] != 0) {
for (int j = 0; j < counting[i]; j++) {
nums[x++] = i;
}
}
}
}
private static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
