排序算法
内部排序和外部排序：
位于内存中的排序叫做内排序，需要使用外存的叫外排序。
排序的稳定性：
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，那么称该排序算法稳定。
如果我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？
最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：**我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。**为什么呢？
稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。在第二次排序中，我们用的是稳定的排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。
总结：
堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法
排序详解
快速排序
1.算法思想：
首先从数组中选取一个基准元素x，比x小的元素放到x左边，比x大的元素放到x右边，然后对于x的左右两边递归执行
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34void Quicksort(int* r, int low, int high)
{
int mid;
if (low < high)
{
mid = partition(r, low, high); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, high); // 右区间递归快速排序
}
int partition(int *r, int low, int high)
{
int i = low, j = high, pivot = r[low];
while(i < j)
{
while (i<j && r[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
{
j--;
}
if (i < j)
{
swap(r[i++], r[j]); //r[i]和r[j]交换后 i 向右移动一位
}
while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
{
i++;
}
if (i < j)
{
swap(r[i], r[j--]); //r[i]和r[j]交换后 i 向左移动一位
}
}
return i; //返回最终划分完成后基准元素所在的位置
}3.时间复杂度：
由于该算法为分治算法，每次将原问题划分成两个规模减半的子问题，划分的额外工作量为O(n)，所以其递推公式为：$T(n) = 2 * T(n/2) + O(n)$
根据主定理可以得到最好（平均）时间复杂度为 $T(n) =\Theta(nlogn)$
最坏的情况是当划分产生的两个子问题的分别包含n和0个元素的时候，此时的时间复杂度是$T(n) =\Theta(n^2)$：
- 数组已经是正序
- 数组已经是倒序
- 所有的元素都相同
这种情况可能因为每次选择最左或者最右的元素作为pivot导致，所以可以通过使用随机的元素作为pivot来解决。
4.空间复杂度：
空间复杂度为$\Theta(logn)$，因为该算法递归调用，每次调用使用常数空间，所以空间复杂度等于递归深度。
**5.稳定性：**不稳定
冒泡排序
1.算法思想：
内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。
外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12public void bubbleSort(int[] nums){
int n = nums.length;
for(int i = 0; i < n-1; i++){
for(int j = 0; j < n - 1 - i; j++){
if(nums[j] > nums[j+1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}**3.时间复杂度：**平均和最坏的时间复杂度是$O(n^2)$，最好的情况是已经有序，复杂度为$O(n)$
**4.空间复杂度：**原地交换元素，空间复杂度为$O(1)$
**5.稳定性：**稳定
选择排序
1.算法思想：
首先在未排序的序列中找出最大的元素，放到排序序列的起始位置。再从剩余未排序序列中找出最大元素，放到已排序序列的末尾。重复第二步直到所有元素排序完成。
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public class SelectionSort implements IArraySort {
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}**3.时间复杂度：**平均、最坏、最好复杂度都是$O(N^2)$
**4.空间复杂度：**原地交换元素，空间复杂度为$O(1)$
**5.稳定性：**不稳定
插入排序
1.算法思想：
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public class InsertSort implements IArraySort {
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数，插入
if (j != i) {
arr[j] = tmp;
}
}
return arr;
}
}3.时间复杂度：
最好情况是完全有序，时间复杂度为$O(n)$，最坏和平均是$O(n^2)$
4.空间复杂度：
原地交换元素，空间复杂度为$O(1)$
**5.稳定性：**稳定
希尔排序
1.算法思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。
首先拿到一个增量序列，例如10,5,2,1，第一趟排序把间隔为10的元素都抽出来为一组（0,10,20……这些是一组，1,11,21……这些是一组），进行排序，第二趟把间隔为5的元素算成一组，进行排序。依次类推。
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}3.时间复杂度：
时间复杂度视增量序列的不同也不同，如果是shell增量序列：$\frac{n}{2},\frac{n}{4} ,\frac{n}{8} …… $，最坏情况为$O(N^2)$，通常来说复杂度为$O(n^{1.3-2})$
**4.空间复杂度：**原地交换元素，空间复杂度为$O(1)$
**5.稳定性：**不稳定
归并排序
1.算法思想：
归并排序运用的是分治思想，将已经有序的子序列合并，得到完全有序的序列。若将两个有序表合并成一个有序表，称为二路归并排序。
2.算法设计：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution {
public int[] sortArray(int[] nums) {
mergesort(nums, 0, nums.length-1);
return nums;
}
private void mergesort(int[] arr, int l , int r){
if(l >= r) return;
int mid = (l+r) / 2;
mergesort(arr, l, mid);
mergesort(arr, mid+1, r);
if(arr[mid] > arr[mid+1]){
merge(arr, l, mid, r);
}
}
private void merge(int[] arr, int l, int mid, int r){
int[] temp = Arrays.copyOfRange(arr, l, r+1);
int i = l;
int j = mid+1;
int k = l;
while(i <= mid && j <= r){
if(temp[i - l] < temp[j - l]){
arr[k++] = temp[i++ - l];
}else{
arr[k++] = temp[j++ - l];
}
}
while(i <= mid){
arr[k++] = temp[i++ - l];
}
while(j <= r){
arr[k++] = temp[j++ - l];
}
}
}3.时间复杂度：
先对区间进行对半划分（$log(n)$层），再逐层进行合并 $O(n)$，总的时间复杂度（平均，最好，最坏）就是$O(nLogn)$。
4.空间复杂度：
合并的时候需要申请线性大小的临时数组，所以空间复杂度是$O(N)$。
**5.稳定性：**稳定
堆排序
1.算法思想：
2.算法设计：
3.时间复杂度：
4.空间复杂度：
5.稳定性：
基数排序
1.算法思想：
2.算法设计：
3.时间复杂度：
4.空间复杂度：
5.稳定性：
计数排序
1.算法思想：
2.算法设计：
3.时间复杂度：
4.空间复杂度：
5.稳定性：
桶排序
1.算法思想：
2.算法设计：
3.时间复杂度：
4.空间复杂度：
5.稳定性：
