排序算法和其时间复杂度
插入排序 堆排序 归并排序 快速排序 是最重要的 稳定不稳定就是指值相同的元素，拍完序之后的相对位置是否会改变（谁在谁的左边）
基本的排序算法
冒泡排序：每次把最大的移到最后面。最好的情况On （但是这个时候需要一个标记，标记元素是否发生改变），最坏的情况On^2 ==>n+n-1+n-2+…+1选择排序：每次找到第n的元素，并与第n-1个元素进行互换。最好的情况On^2（即使是有序的，每次都需要找最小的元素去交换），最坏的情况 On^2(和最好的情况时间复杂度是一样的，只不过多个了交换)。空间复杂度O1 （只需要个常量 temp）稳定性：不稳定插入排序：将第m+1个数插入到前m个已经排好序的元素中，递归。最好的情况On，最坏的情况On^2，空间复杂度O1 稳定性：稳定
二分插入排序：在将第m+1个数插入到前m个已经排好序的元素中去时，采用二分查找的方式查找元素应该插入的位置
常考的排序算法
归并排序 最好的情况==最坏的情况==Onlogn 空间复杂度 On 稳定快速排序
选一个pivot(一般选最右侧元素)有左指针和右指针，当左指针指向一个大于pivot的数，右指针指向一个小于pivot的数，交换。当 l==r 时，当前元素大于pivot，则交换，否则 l+1元素与pivot交换，（保证pivot左侧都小于，右侧都大于）对剩余没有排序的俩个区间进行相同的操作(选pivot…) 这是一个递归的过程最好的情况是 Onlogn ， 最坏的情况是n^2 空间复杂度是 Ologn 不稳定 拓扑排序
其他排序算法
堆排序桶排序
选择排序
每次找出第i小的元素的下标，并与第i位交换
public void sort(int[] nums
){
for (int i
= 0; i
< nums
.length
-1; i
++) {
int t
=i
;
for (int j
= i
; j
<nums
.length
; j
++) {
if(nums
[j
]<nums
[t
]) t
=j
;
}
int temp
=nums
[t
];
nums
[t
]=nums
[i
];
nums
[i
]=temp
;
}
}
插入排序
从第二个元素开始，已插入的方式，插入到该在的位置，其他元素左移或者右移
public void sort(int[] nums
){
for (int i
= 1; i
< nums
.length
; i
++) {
int temp
=nums
[i
],j
=i
;
while (j
>0 && temp
<nums
[j
-1]){
nums
[j
]=nums
[j
-1];
j
--;
}
nums
[j
]=temp
;
}
}
希尔排序
希尔排序是一种高效的插入排序希尔增量gap = length/2 步骤：
希尔排序是先对 数组分成gap组，第i个和第gap+i个进行插入排序之后 数组被分成gap/2组，第i个和第i+gap/2和第gap+i个进行插入排序直到gap/2/2==1，这个 时候做个总的插入排序，时间要快很多
时间复杂度：最好的情况Onlogn , 最坏的情况 On(logn)^2 空间复杂度：O(1) 稳定性：不稳定 因为希尔排序 分组插入，所以不稳定
堆排序
基本思路：先把数组构建成一个大顶堆，然后将堆顶和数组的最后一个元素互换，这样就把最大值移到了最后方，再把数组的n-1重新构建大顶堆，再将堆顶和倒数第二个元素互换。依次类推，直至数组排序完成。 堆重建就是将不满足顶堆规则的元素进行交换
对于一个堆来说：
是一个完全二叉树 （从左致右依次增加）所有父节点的值都要大于（或小于）子节点的值
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序中用于升序排序小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序中用于降序排序 时间复杂度： 最好的情况：Onlogn == 最坏的情况 Onlogn 空间复杂度：O1 稳定性：不稳定 因为得排成二叉树，且存在交换，所以无法确定相同元素的先后顺序
计数排序
基本思路：将数组从头到尾遍历一遍，找到其中的最小值和最大值。并把最小值到最大值中间所有的整数都列举出来，并把所有数字之间出现的次数相加起来。 然后就无需管原数组，将数组按最小到最大以及出现次数 写出就好 用在重复数很多的情况下更好 时间复杂度：最好的情况：O（n+k）==最坏的情况O（n+k） 空间复杂度：O（k） 稳定性：稳定
桶排序
一个进阶版的计数排序（因为计数排序相当于每个桶长度为1的桶排序） 基本思路：分桶，对各个元素放入到相应的桶中，对桶中元素进行排序，然后按桶一次输出 时间复杂度：最好的情况：O（n+k）（k是桶的个数）最坏的情况：O（n^2）(最坏的情况是所有元素都在一个桶里，这样就相当于一个简单的排序) 空间复杂度：O（n+k） 稳定性：稳定(其实稳不稳定，主要看桶内的排序算法，所以不一定是稳定的)
基数排序
基数排序像是一个特殊版本的桶排序，单个桶为0~9,存入按当前位数的数字存。（依次按位进行存入） 基本思路：先按各位存入0～9号桶中(当前位 ==桶号)，之后将上次存入好后的顺序的按十位进行存入，依次反复，直到位数结束，就得到了排好序的数组 时间复杂度：最好的情况下：O(nk) ==最坏的情况下：O（nk）（k为最大数的位数） 空间复杂度：O(n+k) 稳定性：稳定
