排序算法

名称	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	$$O(n^2)$$	$$O(n)$$	$$O(n^2)$$	$$O(1)$$	$$Y$$
选择排序	$$O(n^2)$$	$$O(n^2)$$	$$O(n^2)$$	$$O(1)$$	$$N$$
堆排序	$$O(nlogn)$$	$$O(nlogn)$$	$$O(nlogn)$$	$$O(1)$$	$$N$$
插入排序	$$O(n^2)$$	$$O(n)$$	$$O(n^2)$$	$$O(1)$$	$$Y$$
希尔排序	$$O(nlogn)$$	$$O(n^2)$$	$$O(nlogn)$$	$$O(1)$$	$$N$$
归并排序	$$O(nlogn)$$	$$O(nlogn)$$	$$O(nlogn)$$	$$O(n)$$	$$Y$$
快速排序	$$O(nlogn)$$	$$O(nlogn)$$	$$O(n^2)$$	$$O(logn)$$	$$N$$
计数排数	$$O(n+k)$$	$$O(n+k)$$	$$O(n+k)$$	$$O(k)$$	$$Y$$
桶排序	$$O(n+k)$$	$$O(n+k)$$	$$O(n^2)$$	$$O(n+k)$$	$$Y$$
基数排序	$$O(n\times k)$$	$$O(n\times k)$$	$$O(n\times k)$$	$$O(n+k)$$	$$Y$$

一、冒泡排序

递归版

非递归

public class BubbleSort{public static void sort(int[] a) {}public void bubble(int[] a) {int j = a.length - 1;int x = 0;while (true) {for(int i = 0; i < j - 1; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);x = i;  }}j = x;if (j == 0) {break;}}}private void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

二、选择排序

public class SelectSort{public static void sort(int[] a) {for(int i = a.length - 1; i > 0; i--) { int max = i;for(int j = 0; j < i; j++) {if (a[j] > a[max]) {max = j;}}if (max != i) {swap(a, i, max);} }}private void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}   
}

堆排序

public class HeapSort() {public static void sort(int[] a) {heapify(a, a.length);for(int i = a.length - 1; i > 0; i--) {swap(a, 0, i);down(a, 0, i);}}public static void heapify(int[] array, int size) {for(int i = size / 2 - 1; i >= 0; i--) {down(array, i, size);}}public static void down(int[] array, int parent, int size) {int left = 2 * parent + 1;int right = left + 1;int max = parent;if (left < size && array[left] > array[max]) {max = left;}if (right < size && array[right] > array[max]) {max = right;}if (max != parent) {swap(array, max, parent);down(array, max, size);}}public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}

插入排序

递归实现

public class InsertSort{public static void sort(int[] a) {insert(a, 1);}public static void insert(int[] a, int low) {if (low == a.length) {return ;}int t = a[low];int i;for(i = low - 1; i >= 0 && a[i] > t; i--) {a[i + 1] = a[i];}if (i + 1 != low) {a[i + 1] = t;}insert(a, low + 1);}
}

public class InsertSort{public static void sort(int[] a) {insert(a, 1);}public static void insert(int[] a, int low) {if (low == a.length) {return;}int temp = a[low];int i = low - 1;while (i >= 0; a[i] > temp) {a[i + 1] = a[i];i--;}if (i + 1 != low) {a[i + 1] = temp;}insert(a, low + 1);}
}

非递归实现

public class InsertSort {public static void sort(int[] a) {for(int i = 1; i < a.length; i++) {int temp = a[i];for(int j = i - 1; j >= 0 && a[j] > a[i]; j--) {a[j + 1] =a[j];}if(j != i - 1) {a[j + 1] = temp;}}}
}

public class InsertSort {public static void sort(int[] a) {for(int i = 1; i < a.length; i++) {int temp = a[i];int j = i - 1;while (j >= 0 && a[j] > temp) {a[j + 1] = a[j];}if(j != i - 1) {a[j + 1] = temp;}}}
}

希尔排序

public class ShellSort{public static void sort(int[] a){for(int gap = a.length >> 1; gap >= 1; gap = gap >> 1) {for(int i = gap; i < a.length; i++) {int temp =  a[i];int j = i - gap;while (j >= 0 && a[j] > temp) {a[j + gap] = a[j];j -= gap;}if (j + gap != i) {a[j + gap] = temp;}}}}
}

归并排序

递归方法

public class MergeSort{public static void sort(int[] a) {int[] a2 = new int[a.length];merge(a, 0, a.length - 1, a2);}public static void split(int[] a, int left, int right, int[] a2) {if (left == right) {return;}int m = (left + right) >>> 1;split(a, left, m, a2);split(a, m + 1, right, a2);// 合并操作merge(a, left, m, m + 1, right, a2);System.arraycopy(a2, left, a, left, right - left + 1);}public static void merge(int[] a1, int i, int iend, int j, int jend, int[] a2) {int k = i;while (i <= iend && j <= jend) {if (a1[i] <= a1[j]) {a2[k] = a1[i];i++;} else {a2[k] = a1[j];j++;}k++;}if (i > iend) {System.arraycopy(a1, j, a2, k, jend - j + 1);} if (j > jend) {System.arraycopy(a1, i, a2, k, iend - i + 1);}}
}

非递归方式

归并加插入

public class MergeInsertionSort{public static void insertion(int[] a, int left, int right) {for(int i = left + 1; i <= right; i++) {int t = a[i];int j = i - 1;while (j >= left && a[j] > t) {a[j + 1] = a[j];j--;}if (i != j + 1) {a[j + 1] = t;}}}public static void merge(int[] a, int i, int iend, int j, int jend, int[] a2) {int k = 0;while (i <= iend && j <= jend) {if (a[i] <= a[j]) {a[k] = a[i];i++;} else {a[k] = a[j];j++;}k++;}if (j > jend) {System.arraycopy(a, i, a2, k, iend - i + 1);}if (i > iend) {System.arraycopy(a, j, a2, k, jend - j + 1);}}public static void split(int[] a, int i, int j, int[] a2) {if (i == j) {// 插入排序insertion(a, i, j);return;}int m = (i + j) >>> 1;split(a, i, m);split(a, m + 1, j);// 合merge(a, i, m, m + 1, j, a2);System.arraycopy(a2, left, a, left, j - i + 1);}
}

快排

单边循环

public class QuickSortLomuto{public static void sort(int[] a) {quick(a, 0, a.length - 1);}public static void quick(int[] a, int left, int right) {if (left >= right) {return;}int p = partition(a, left, right);quick(a, left, p - 1);quick(a, p + 1, right);}public static int partition(int[] a, int left, int right) {int pv = a[right];int i = left;int j = right;while (i < j) {if (a[j] < pv) {if (i != j) {swap(a, i, j);}i++;}j++;}swap(a, i, right);return i;}public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}

双边循环

注意事项

• 加内层循环的i < j 条件
• 先处理j，后处理i
• 随机元素作为基准点

public class QuickSortLomuto{public static void sort(int[] a) {quick(a, 0, a.length - 1);}public static void quick(int[] a, int left, int right) {if (left >= right) {return;}int p = partition(a, left, right);quick(a, left, p - 1);quick(a, p + 1, right);}public static int partition(int[] a, int left, int right) {int pv = a[left];int i = left;int j = right;while (i < j) {while (i < j && a[j] > pv) {j--;}while (i < j && a[i] <= pv) {i++;}swap(a, i, j);}swap(a, left, i);return i;}public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}

改进

public class QuickSortLomuto{public static void sort(int[] a) {quick(a, 0, a.length - 1);}public static void quick(int[] a, int left, int right) {if (left >= right) {return;}int p = partition(a, left, right);quick(a, left, p - 1);quick(a, p + 1, right);}public static int partition(int[] a, int left, int right) {int pv = a[left];int i = left;int j = right;while (i <= j) {while (i <= j && a[i] < pv) {i++;}while (i <= j && a[j] > pv) {j--;}if (i <= j) {swap(a, i, j);}}swap(a, left, j);return j;}public static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}
}

计数排序

public class CountSort{public static void sort(int[] a) {int max = a[0];for(int num : a) {if (num > max) {max = num;}}int[] counts = new int[max + 1];for(int i = 0; i < a.length; i++) {counts[a[i]]++;}int k = 0;for(int i = 0; i < count.length; i++) {while (count[i] > 0) {a[k++] = i;count[i]--;}}} 
}

代码改进

public class CountSort{public static void sort(int[] a) {int max = a[0];int min = a[0];for(int num : a) {if (num > max) {max = num;}if (num < min) {min = num;}}int[] counts = new int[max - min + 1];//for(int i = 0; i < a.length; i++) {//    counts[a[i]]++;//}// 使用增强for循环for(int num : a) {counts[num - min]++;}int k = 0;for(int i = 0; i < counts.length; i++) {while (counts[i] > 0) {a[k++] = i + min;count[i]--;}}} 
}

桶排序

public clsss BucketSor{public static void sort(int[] a) {List buckets = new ArrayList[10];for(int i = 0; i < a.length; i++) {buckets[i] = new ArrayList();}for(int num : a) {buckets[num % 10] = num;}int k = 0;for(List bucket : buckets) {int[] array = new int[bucket.size()];if (bucket.size() > 0) {for(int i = 0; i < bucket.size(); i++) {array[i] = bucket.get(i);}}InsertSort.sort(array);for(int i : array) {a[k++] = i;}}} 
}

基数排序

public class RadixSort{public static void sort(String[] a, int length) {ArrayList<String>[] buckets = new ArrayList<>[10];for(int i = 0; i < 10; i++) {buckets[i] = new ArrayList<>();}for(int i = length - 1; i >= 0; i--) {for(String s : a) {bucket[s.charAt(i) - '0'].add(s);}int k = 0;for(ArrayList<String> bucket : buckets) {for(String s : bucket) {a[k++] = s;}bucket.clear();}}} 
}