排序算法是比较基础，且比较重要的数据结构内容。今天在这里简单总结一下基本原理、代码和注意事项，让自己有一个比较全面的了解，也能方便查看。
本文一共讲了选择排序、冒泡排序、快速排序、归并排序、插入排序、希尔排序、堆排序、桶排序、基数排序九种排序算法。
选择排序
循环中每次选择要排序记录中最小的一个和最前面的交换。换上n趟，就排好啦~
-
时间复杂度：
O(n^2)
public int[] selectSort(int[] input) {
for (int i = 0; i < input.length; i++) {
int min = input[i];
int index = i;
for (int j = i + 1; j < input.length; j++) {
if (input[j] < min) {
min = input[j];
index = j;
}
}
int temp = input[i];
input[i] = input[index];
input[index] = temp;
}
return input;
}
冒泡排序
一趟排序中依次比较相邻的两个，如果前面的大于后面的就交换，这样一趟下来最大的一定会到最后一位。然后运行n趟，这整个为n的记录就排好序了。
-
时间复杂度：
O(n^2)
public int[] bubbleSort(int[] input) {
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length - 1 - i; j++) {
if (input[j] > input[j + 1]) {
int temp = input[j];
input[j] = input[j + 1];
input[j + 1] = temp;
}
}
}
return input;
}
快速排序
每一次排序都会把待排序的记录分成两部分，其中一部分均比另一部分小，然后再对这两两部分分别排序，直到完全有序。
- 具体做法：选择记录中第一个数字作为关键字，将传入的左边界和右边界作为左右指针，先循环减少右指针寻找右边小于关键字的挪到左指针的位置，然后再循环增加左指针从左边找大于关键字的挪到右指针位置，直到左指针等于右指针，然后将关键字赋到这个位置。然后再递归调用这两部分。直到结束。
-
时间复杂度：
O(nlogn) -
注意：排序算法被认为是相同时间复杂度里平均性能最好的。如果序列基本有序会退化为冒泡排序，时间复杂度为
O（n^2）。
public int[] quickSort(int[] input, int low, int height) {
if (low >= height) {
return null;
}
int left = low;
int right = height;
int key = input[left];
while (left < right) {
while (left < right && input[right] >= key) {
right--;
}
input[left] = input[right];
while (left < right && input[left] <= key) {
left++;
}
input[right] = input[left];
}
input[left] = key;
quickSort(input, low, left - 1);
quickSort(input, right + 1, height);
return input;
}
归并排序
采用递归的方法，将待排序的记录分成几个有序的小部分，然后再进行合并。
- 具体做法：递归的将记录分为最小部分，然后再从合并中排序。合并的过程中，先从两个的左边开始比较，如果较小就放到临时数组里，直到有一方空了，再把另一个数组的剩余部分全部放进临时数组里。然后再把临时数组重新放到原数组。最后合并为一个完全有序的记录。
-
时间复杂度：
O(nlogn) -
空间复杂度：
O(n)
public void mergeSort(int[] input, int low, int height) {
if (low < height) {
int mid = (low + height) / 2;
mergeSort(input, low, mid);
mergeSort(input, mid + 1, height);
merge(input, low, height);
}
}
public void merge(int[] input, int left, int right) {
int[] temp = new int[input.length];
int mid = (left + right) / 2;
int index = left;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right) {
if (input[i] < input[j]) {
temp[index++] = input[i++];
} else {
temp[index++] = input[j++];
}
}
while (i <= mid) {
temp[index++] = input[i++];
}
while (j <= right) {
temp[index++] = input[j++];
}
for (int a = left; a <= right; a++) {
input[a] = temp[a];
}
}
直接插入排序
将一个记录插入到已经排好序的有序表中，得到一个新的、记录数增一的有序表。
- 形象描述：就像打牌的时候，我们每抓一张牌都会把这张牌插入到已经排好顺序的牌里面。
- 具体做法：外层循环从1到n-1。内层循环查看当前数字是否比前一个数字小，如果大的话就跳过，如果小就要循环已排好序数列，然后将当前数字插入到合适位置。
-
时间复杂度：
O(n^2) -
注意：在基本有序情况下，直接插入算法是最快的排序算法，时间复杂度为
O（n）
public int[] straightInsertionSort(int[] input) {
for (int i = 1; i < input.length; i++) {
int temp = input[i];
int j;
for (j = i - 1; j >= 0 && temp < input[j]; j--) {
input[j + 1] = input[j];
}
input[j + 1] = temp;
}
return input;
}
希尔排序
先将整个待排序记录分为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再进行一次直接插入排序。
-
具体实现：先选择插入的距离为
length/2完成第一次插入排序，然后再从原来的基础上/2,最后当距离变成1的时候就变成了直接插入排序。 - 时间复杂度：不好说，但肯定比直接插入排序智能点。
public int[] shellSort(int[] input) {
int dk = input.length / 2;
while (dk > 0) {
for (int i = dk; i < input.length; i++) {
int temp = input[i];
int j;
for (j = i - dk; j >= 0 && temp < input[j]; j -= dk) {
input[j + dk] = input[j];
}
input[j + dk] = temp;
}
dk /= 2;
}
return input;
}
堆排序
先将记录转化为最大堆或者最小堆，然后不断地将第一个数字拿出来存储，然后调整堆，最后堆为空的时候，排序完成。
- 具体视线：首先生成堆，然后把堆的第一个元素和最后一个元素交换，减少堆的长度。然后重新把被破坏了的堆重新调整成堆。然后再完成交换，直到结束。
-
时间复杂度：
O(nlogn)
public int[] heapSort(int[] input) {
buildHeap(input);
for (int i = input.length - 1; i >= 0; i--) {
int t = input[i];
input[i] = input[0];
input[0] = t;
adjustHeap(input, 0, i);
}
return input;
}
private void buildHeap(int[] input) {
for (int i = (input.length - 1) / 2; i >= 0; i--) {
adjustHeap(input, i, input.length);
}
}
private void adjustHeap(int[] input, int s, int length) {
int temp = input[s];
int child = 2 * s + 1;
while (child < length) {
if (child + 1 < length && input[child + 1] > input[child]) {
child++;
}
if (input[child] > input[s]) {
input[s] = input[child];
input[child] = temp;
s = child;
child = 2 * s + 1;
} else {
break;
}
}
}
桶排序
新建一个容量为最大数字+1个的数组空间。然后把每个数直接放到该数组与自己对应的地方，然后按次序拿出来就好了。
-
时间复杂度：
O(n) - 注意：考虑负数和有相同数字的情况，本程序没考虑。
public int[] bucketSort(int[] input, int max) {
int[] temp = new int[max + 1];
for (int i = 0; i < input.length; i++) {
temp[input[i]] = input[i];
}
int index = 0;
for (int i = 0; i < max + 1; i++) {
if (temp[i] != 0) {
input[index++] = temp[i];
}
}
return input;
}
基数排序
分别以各位数字进行桶排序，然后按顺序取出，遍历完所有位遍完成排序。
- 具体实现：先建立一个二维数组，然后将个位上相同的数字放进同一个桶，然后依次取出放回原数组，这样就实现了个位上的有序，然后百位，千位，最后遍历完成所有位即完成排序。
-
时间复杂度：
O(d(n+rd)) -
空间复杂度：
O(rd) - 注意：要考虑存在负数的情况。本程序里没有考虑。
public int[] radixSort(int[] input, int max) {
int[][] temp = new int[10][input.length];
int[] num = new int[10];
int index = 1;
int n = 1;
while (index <= max) {
for (int i = 0; i < input.length; i++) {
int wei = input[i] / n % 10;
temp[wei][num[wei]++] = input[i];
}
int count = 0;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < input.length; j++) {
if (temp[i][j] == 0) {
break;
} else {
input[count++] = temp[i][j];
}
}
}
for (int i = 0; i < 10; i++) {
num[i] = 0;
for (int j = 0; j < input.length; j++) {
temp[i][j] = 0;
}
}
index++;
n *= 10;
}
return input;
}
就酱~
欢迎关注【Funny新青年】微信公众号～
