排序算法整理
2018-06-14 本文已影响1人
iszhenyu
首先需要声明的是，本文并不会探讨每个算法内部的逻辑，而主要以代码实现和结论为主，需要了解具体原理的同学可以参考《算法导论》一书。
从大的方向上来说，排序算法可以分为内部排序和外部排序两种，内部排序 指的是整个排序过程不需要借助于外部存储器（比如磁盘），所有排序操作都可以在内存中完成。而如果参与排序的数据元素非常多，数据量非常大，则无法把整个排序过程放在内存中完成，必须借助于外部存储器（比如磁盘），这种排序算法又称为 **外部排序 **。
内部排序如果再进一步细分的话，又可以划分为下图中的一些算法。
image
直接选择排序
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 2; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
Common.swap(arr, i, minIdx);
}
}
}
堆排序
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
public static void sort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
buildMaxHeap(arr, i);
Common.swap(arr, 0, i);
}
}
private static void buildMaxHeap(int[] arr, int end) {
if (end > 0) {
int firstNoneLeaf = (end - 1) / 2;
for (int j = firstNoneLeaf; j >= 0; j--) {
maxHeapify(arr, j, end);
}
}
}
private static void maxHeapify(int[] arr, int i, int end) {
int leftChild = (i << 1) + 1;
int rightChild = leftChild + 1;
int maxIdx = i;
if (leftChild <= end && arr[leftChild] > arr[maxIdx]) {
maxIdx = leftChild;
}
if (rightChild <= end && arr[rightChild] > arr[maxIdx]) {
maxIdx = rightChild;
}
if (maxIdx != i) {
Common.swap(arr, i, maxIdx);
maxHeapify(arr, maxIdx, end);
}
}
归并排序
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
- 稳定性：稳定
public static void sort(int[] arr) {
int size = arr.length;
divide(arr, 0, size - 1);
}
private static void divide(int[] arr, int left, int right) {
if (left < right) {
int center = left + (right - left) / 2;
sub_sort(arr, left, center);
sub_sort(arr, center + 1, right);
merge(arr, left, center, center + 1, right);
}
}
private static void merge(int[] oriArr, int left1, int right1, int left2, int right2) {
int[] assistArr = new int[oriArr.length];
int pointer1 = left1;
int pointer2 = left2;
int tmp = left1;
while (pointer1 <= right1 && pointer2 <= right2) {
if (oriArr[pointer1] < oriArr[pointer2]) {
assistArr[tmp] = oriArr[pointer1];
pointer1++;
} else {
assistArr[tmp] = oriArr[pointer2];
pointer2++;
}
tmp++;
}
while (pointer1 <= right1) {
assistArr[tmp] = oriArr[pointer1];
tmp++;
pointer1++;
}
while (pointer2 <= right2) {
assistArr[tmp] = oriArr[pointer2];
tmp++;
pointer2++;
}
tmp = left1;
while (tmp <= right2) {
oriArr[tmp] = assistArr[tmp];
tmp++;
}
}
冒泡排序
- 时间复杂度：最好的情况下是O(n)，最坏情况下是O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定
public static void sort(int[] arr) {
int size = arr.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
Common.swap(arr, j, j + 1);
}
}
}
}
快速排序
- 时间复杂度：O(nlogn)
- 空间复杂度：由于快排使用了递归，递归是需要栈的，因此空间复杂度为O(logn)
- 稳定性：不稳定
public static void sort(int[] arr) {
int size = arr.length;
quickSort(arr, 0, size - 1);
}
private static void quickSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int left = start + 1;
int right = end;
int pivot = arr[start];
// 当start + 1 == end时，也要进while一次，否则下面直接swap会出错，所以这里必须是<=
while (left <= right) {
// 从左侧开始找到第一个大于pivot的值，结果是要么找到，要么越界
while (left <= end && arr[left] <= pivot) {
left++;
}
// 从右侧开始找到第一个小于pivot的值，结果是要么找到，要么越界
while (right >= start + 1 && arr[right] >= pivot) {
right--;
}
// 这里left不可能等于right，如果left==right则意味着一个数既大于pivot又小于pivot，显然是矛盾的
if (left < right) {
Common.swap(arr, left, right);
}
}
// 当right停在比pivot小的元素时，直接交换
// 如果right越界，则right == start
Common.swap(arr, start, right);
subSort(arr, start, right - 1);
subSort(arr, right + 1, end);
}
计数排序
/**
* 计数排序
* @param input 输入待排序数组
* @param output 排序后的输出数组
* @param k 输入数组的每个元素在[0, k]之间
*/
public static void sort(int[] input, int[] output, int k) {
// 创建0-k的数组，并初始化为0
int[] base = new int[k + 1];
// 对于input中的每个元素，如果值i出现一次，则相应的base[i]加1
// 最终base数组中每个位置的数值大小代表了取该值的元素数量
for (int i = 0; i < input.length; i++) {
base[input[i]] += 1;
}
// 因为base是已经排序好了的，所以从索引0开始，将当前索引处的值加到下一个索引的值上
// 最后base数组每个元素的值大小，代表了有多少个元素小于等于当前索引的大小
for (int i = 1; i <= k; i++) {
base[i] += base[i - 1];
}
for (int i = 0; i < input.length; i++) {
int index = base[input[i]];
output[index - 1] = input[i];
base[input[i]] -= 1;
}
}
public static void sort2(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
int cur = arr[i];
if (cur > max) {
max = cur;
}
if (cur < min) {
min = cur;
}
}
int k = max - min + 1;
int[] assist = new int[k];
for (int i = 0; i < arr.length; i++) {
assist[arr[i] - min] += 1;
}
for (int i = 0; i < k; i++) {
// 当前位置元素数量
int count = assist[i];
if (i > 0) {
assist[i] += assist[i - 1];
}
int curVal = i + min;
int maxIdx = assist[i];
if (count == 1) {
arr[maxIdx - 1] = curVal;
} else {
for (int j = 0; j < count; j++) {
arr[maxIdx - 1] = curVal;
maxIdx--;
}
}
}
}
基数排序
public static void lsdSort(int[] arr) {
int size = arr.length;
int maxVal = 0;
for (int i = 0; i < size; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
int[][] assist = new int[10][size];
int[] assistCount = new int[10];
int digitPos = 1;
while (maxVal / digitPos > 0) {
for (int i = 0; i < size; i++) {
int cur = arr[i];
int radix = (cur / digitPos) % 10;
assist[radix][assistCount[radix]] = cur;
assistCount[radix]++;
}
int idx = 0;
for (int i = 0; i < 10; i++) {
int count = assistCount[i];
if (count > 0) {
for (int j = 0; j < count; j++) {
arr[idx] = assist[i][j];
idx++;
}
// assistCount 清零
assistCount[i] = 0;
}
}
digitPos *= 10;
}
}
桶式排序
private static class Node {
int data;
Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
}
public static void sort(int[] input, int[] output, int bucketSize) {
Node[] bucket = new Node[bucketSize];
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new Node(); // 头结点
}
for (int i = 0; i < input.length; i++) {
int bucketIndex = hash(input[i]);
Node node = new Node(input[i]);
Node p = bucket[bucketIndex];
if (p.next == null) { // 没有元素
p.next = node;
} else { // 已经有一个元素
while (p.next != null && p.next.data <= node.data) {
p = p.next;
} // 跳出循环时候 该值小于下一个元
node.next = p.next;
p.next = node;
}
}
int j = 0;
for (int i = 0; i < bucket.length; i++) {
for (Node p = bucket[i].next; p != null; p = p.next) { // n/m
output[j++] = p.data;
}
}
}
private static int hash(int value) {
return value / 10;
}
直接插入排序
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}
折半插入排序
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int index = binarySearch(arr, arr[i], i - 1);
for (int j = i - 1; j >= index; j--) {
arr[j + 1] = arr[j];
}
arr[index] = tmp;
}
}
private static int binarySearch(int[] arr, int target, int maxIndex) {
int find = 0;
while (find <= maxIndex) {
int mid = (find + maxIndex) / 2;
if (target > arr[mid]) {
find = mid + 1;
} else {
maxIndex = mid - 1;
}
}
return find;
}
Shell排序
public static void sort(int[] a) {
int n = a.length;
int h = 1;
while (h < n / 3) {
h = h * 3 + 1;
}
while (h >= 1) {
for (int group = 0; group < h; group++) {
subSort(a, group, h);
}
h = (h - 1) / 3;
}
}
private static void subSort(int[] a, int start, int gap) {
for (int i = start + gap; i < a.length; i += gap) {
int item = a[i];
int j = i;
while (j > start && item < a[j - gap]) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = item;
}
}
完！
