各种排序算法如下：
【可参考下面的两篇文章，写的都非常好。】
1.冒泡排序： 为内排序、稳定排序。
时间复杂度：平均情况：T(n) = O(n^2),最佳情况：T(n) = O(n),最差情况：T(n) = O(n^2)
空间复杂度：O(1) 、原地排序。
思想（若是需要前小后大就如此，否则反过来）：重复走访要比较的序列，一次比较两个元素，两个元素间大的往后放，小的往前放，最后越小的元素会慢慢冒泡至顶端。
冒泡排序最坏情况比较次数： (n-1)+(n-2)+(n-3)+…+1=n(n-1)/2。故为O(n^2)。 最坏情况下，每一轮该元素要和其他每一个元素进行比较。
最坏情况举例： 9 8 7 6 5 4 3 2 1
最好情况：O(n)，即为按顺序排列，只进行一次比较即可。
最好情况举例：1 2 3 4 5 6 7 8 9
理解：最好情况和最坏情况的区别是进不进入第二个for循环里的if处理。
稳定：是因为相等的时候不会交换。
func bubbleSort(arr []int) []int {
if len(arr) == 0 || len(arr) == 1 {
return arr
}
// 从前往后冒泡，每次把大的往后放：
for i := 0; i < len(arr); i ++ {
for j := 0; j < len(arr)-1-i; j ++ {// len(arr)-1-i缩小需要比较的区间
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
2.选择排序：为内排序、不稳定。
时间复杂度：平均情况：T(n) = O(n^2),最佳情况：T(n) = O(n^2),最差情况：T(n) = O(n^2),
空间复杂度：O(1)、原地排序。
因为无论什么数据进去都是O(n^2)的时间复杂度，因此用它的时候，数据规模越小越好。
不稳定——比如有4443，排序的时候会把第一个4和3交换，故本来在前面的4的位置去后面了。
思想(仍以前小后大为例)：`将数组分为有序区和无序区，先在未排序序列中选择一个最小的数 放在（直接交换）排序序列的起始位置。然后再从未排序序列中找到最小元素，放到已排序序列的末尾。以此类推直到排序完毕。直接交换
func selectionSort(arr []int) []int {
if len(arr) == 0 || len(arr) == 1 {
return arr
}
for i := 0; i < len(arr); i ++ {
min := i
// 这里要从i开始走完完整的一遍后，才能确定哪个下标对应的元素为最小值
for j := i; j < len(arr); j ++ {
if arr[j] < arr[min] {
min = j
}
}
arr[min], arr[i] = arr[i], arr[min]// 0到i是已排序区间，i后面的是未排序区间
}
}
3.插入排序：内排序、稳定。
时间复杂度：平均情况：T(n) = O(n^2), 最佳情况：T(n) = O(n), 最差情况：T(n) = O(n^2)
空间复杂度：O(1),原地排序。
思路：构建有序序列，对于未排序序列中的数据，在已排序序列中从后向前扫描，找到相应位置并插上。在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
func insertionSort(arr []int) []int {
if len(arr) == 0 || len(arr) == 1 {
return arr
}
for i := 0; i < len(arr)-1; i ++ {
cur := arr[i+1]
pre := i
for pre >= 0 && cur < arr[pre] {
arr[pre+1] = arr[pre]
pre --
}
arr[pre+1] = cur
}
return arr
}
4.希尔排序：也称为缩小增量排序。内排序、不稳定。
时间复杂度：平均情况：T(n) = O(nlogn), 最佳情况：T(n) = O(nlogn), 最差情况：T(n) = O(nlogn)
空间复杂度：O(1)，原地排序。
它与插入排序的不同之处在于，它会优先比较距离较远的元素。
不稳定是因为，有可能两个4在不同组里，后面的那个4是其所在组中较小的值，就会被放在前面去。
思路：将整个待排序的记录序列按照希尔增量分割成若干个子序列，再分别进行直接插入排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
func shellSort(arr []int) {
len := len(arr)
tmp, gap = len / 2
for gap > 0 {
for i := gap; i < len; i ++ {
tmp = arr[i]
preIndex = i - gap
for preIndex >= 0 && arr[preIndex] > tmp {
arr[preIndex + gap] = arr[preIndex]
preIndex -= gap
}
arr[preIndex+gap] = tmp
}
gap /= 2
}
return arr
}
5.归并排序：outplace、稳定。
时间复杂度：平均情况：T(n) = O(nlogn), 最佳情况：T(n) = O(n), 最差情况：T(n) = O(nlogn)
空间复杂度：O(n)，非原地排序，需要额外空间，
思路：采用分治法——将已排序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
步骤：
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
mid := len(arr)/2
left := arr[:mid+1]
right := arr[mid+1:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
result := make([]int, len(left)+len(right))
for index, i, j := 0; i < len(result); index ++ {
if i >= len(left) {
result[index] = right[j]
j ++
} else if j >= len(right) {
result[index] = right[j]
i ++
} else if left[i] > right[j] {
result[index] = right[j]
j ++
} else {
result[index] == left[i]
i ++
}
}
return result
}
6.快速排序：inplace、不稳定。
时间复杂度：平均情况：T(n) = O(nlogn), 最佳情况：T(n) = O(n), 最差情况：T(n) = O(nlogn)
空间复杂度：O(logn)
基本思想：使用分治法把一个串分为两个子串。
先在左边固定一个，然后给一个左指针从他后面的位置开始，右指针从最后位置开始，开始分别往右和往左遍历，当左边遍历到比固定数大的数&&右边遍历到比固定数小的数时，交换左右指针对应的元素位。然后等到左右指针相邻了，就交换固定的数和左指针对应的数。然后继续对下面的区间快排。
就相当于找到每一个元素本该在的位置
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取中轴元素所处的位置
int mid = partition(arr, left, right);
//进行分割
arr = quickSort(arr, left, mid - 1);
arr = quickSort(arr, mid + 1, right);
}
return arr;
}
private static int partition(int[] arr, int left, int right) {
//选取中轴元素
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
// 向右找到第一个小于等于 pivot 的元素位置
while (i <= j && arr[i] <= pivot) i++;
// 向左找到第一个大于等于 pivot 的元素位置
while(i <= j && arr[j] >= pivot ) j--;
if(i >= j)
break;
//交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
// 使中轴元素处于有序的位置
arr[j] = pivot;
return j;
}
}
7.堆排序：inplace、非稳定排序。
时间复杂度：平均情况：T(n) = O(nlogn), 最佳情况：T(n) = O(nlogn), 最差情况：T(n) = O(nlogn),
空间负责度：O(1)，原地排序。
堆排序详解：
思路：堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。
什么是堆：
堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
很多博客说堆是完全二叉树，其实并非如此，堆不一定是完全二叉树，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆，事实上，广为人知的斐波那契堆和二项堆就不是完全二叉树,它们甚至都不是二叉树。
public class HeapSort {
/**
* 下沉操作，执行删除操作相当于把最后一个元素赋给根元素之后，然后对根元素执行下沉操作.
* @param arr
* @param parent 要下沉元素的下标
* @param length 数组长度
*/
public static int[] downAdjust(int[] arr, int parent, int length) {
//临时保证要下沉的元素
int temp = arr[parent];
//定位左孩子节点位置
int child = 2 * parent + 1;
//开始下沉
while (child < length) {
//如果右孩子节点比左孩子小，则定位到右孩子
if (child + 1 < length && arr[child] > arr[child + 1]) {
child++;
}
//如果父节点比孩子节点小或等于，则下沉结束
if (temp <= arr[child])
break;
//单向赋值
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
arr[parent] = temp;
return arr;
}
//堆排序
public static int[] heapSort(int[] arr, int length) {
//构建二叉堆
for (int i = (length - 2) / 2; i >= 0; i--) {
arr = downAdjust(arr, i, length);
}
//进行堆排序
for (int i = length - 1; i >= 1; i--) {
//把堆顶的元素与最后一个元素交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//下沉调整
arr = downAdjust(arr, 0, i);
}
return arr;
}
//测试
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 5,2, 0,10,6};
System.out.println(Arrays.toString(arr));
arr = heapSort(arr, arr.length);
System.out.println(Arrays.toString(arr));
}
}
8.计数排序：适合于最大值和最小值的差值不是很大的排序。
1、时间复杂度：O(n+k) 2、空间复杂度：O(k) 3、稳定排序 4、非原地排序
思路：使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
时间复杂度：最佳情况：T(n) = O(n+k), 最差情况：T(n) = O(n+k), 平均情况：T(n) = O(n+k)
9.桶排序：
1、时间复杂度：O(n+k) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
思路：是计数排序的升级版，利用了函数的映射关系，高效与否取决于映射函数的确定。
时间复杂度：最佳情况：T(n) = O(n+k), 最差情况：T(n) = O(n+k), 平均情况：T(n) = O(n^2)
10.基数排序：
1、时间复杂度：O(kn) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
时间复杂度：最佳情况：T(n) = O(n+k), 最差情况：T(n) = O(n+k), 平均情况：T(n) = O(n+k)