概述
- 排序原理
- 选择排序：遍历比较数组最大值，通过游标标记，最后和末位交换。2个for循环和index解决问题。
- 冒泡排序：遍历比较最大值，不停交换最大值一直到末位，2个for循环解决问题。
- 插入排序：维护一个递增的数组，通过一个指针，和最大的数比，比最大的大就break；否则指针和比较对象都左移
- 希尔排序：3层for循环+while，插入排序的改进版本，跨度插入排序形成基本有序数组再插入排，步长从n/2 变小一直到1
- 快排排序：每次首位元素通过交换找到它在该数组段中的位置，再递归，引入low high head tail关键标记位。基于这种思路，可以解决无序数组中中位数，和无需数组求中位数的算法，随机第一个元素切分数组，缩小范围的方式来定位查找目标。
- 归并(分治)：精华是拆分问题，把数组拆分成2个连续的小数组最后在递归性的从小问题解决到最大的问题，第二个核心在于2个连续的有序数组的merge方法。利用一个辅助数组。递归+三层while循环+3个指针实现
- 堆排序：初始化的时候构建最大堆（调用 2/N ++以上的Node挨个swim），然后和末尾交换位置，下标自减，调用sink()即可
- 空间复杂度：
- 归并排序依赖辅助数组，空间复杂度为N（Merge函数调用时，需要先写到辅助数组中，最后再写回到原数组)
- 快速排序因为递归的次数（N-LogN次）（最差和最好），递归时要保存一些数据
- 其它排序的空间复杂度都是1，常数级别
- 平均时间复杂度
- 冒泡、选择、插入排序 N²
- 希尔排序 N<实际<N²
- 快排、归并、堆排 N*LogN
选择排序
for(int i=0;i<length;i++){
int max=0;
for(int j=1;j<length-i;j++){
if(arr[max]<arr[j]){
max=j;
}
}
Util.exchange(max, length-i-1, arr);
}
插入排序
for(int i=1;i<length;i++){
int index=i;
while(index>0){
if(arr[index]>arr[index-1]) break;
Util.exchange(index, index-1, arr);
index--;
}
}
Shell
public static void shellSortByGap(int gap, int[] arr){
int length=arr.length;
for(int i=0;i<gap;i++){
for(int j=i+gap;j<length;j=j+gap){
int index=j;
while(index>i){
if(arr[index]>arr[index-gap]) break;
if(arr[index]<arr[index-gap]){
Util.exchange(index-gap, index, arr);
index-=gap;
}
}
}
}
}
Quick
public void quickSort(int[] arr,int low,int high){
if(low>=high) return;
int index=low;
int tail=high;
while(index<tail){
if(arr[index]<arr[index+1]){
Util.exchange(tail--, index+1, arr);
}else{
Util.exchange(index, ++index, arr);
}
}
quickSort(arr,low,index-1);
quickSort(arr,index+1,high);
}
heap
public void sink(int k){
//check是否有子节点
while(2*k<=size){
int bigSonNode=2*k;
//如果有右子节点且右子节点大于左子节点则 最大子节点指向右子节点
if((2*k+1<size)&&list.get(2*k)<list.get(2*k+1)){
bigSonNode=2*k+1;
}
//比较左子节点，如果小于，就交换
if(list.get(k)<list.get(bigSonNode)){
Util.exchangeList(k, bigSonNode, list);
k=bigSonNode;
//检查是否存在右子树，如果右且大于父节点就交换
}else{
break;
}
}
}
//通过从N/2开始往堆顶进行sink()操作构建堆有序
public static void buildHeap(MaxPQ pq){
int N=pq.list.size()-1;
for(int i=N/2;i>0;i--){
pq.sink(i);
}
}
public static void HeapSort(MaxPQ pq){
List<Integer> list=pq.getList();
int size=list.size();
int tail=size-1;
for(int i=1;i<size;i++){
Util.exchangeList(1, tail, list);
pq.setSize(--tail);
pq.sink(1);
}
}
Merge
public static void mergeSort(int[] arr,int[] help,int low,int high){
if(low>=high) return;
int middle=(low+high)/2;
mergeSort(arr,help,low,middle);
mergeSort(arr,help,middle+1,high);
merge(arr,help,low,middle,high);
}
//解决的是一个数组被分成2个连续的有序的数组
//第一个有序数组 arr[head]到arr[middle]，第二个有序数组 arr[middle+1]到 arr[tail]
public static void merge(int[] arr,int[] help,int head,int middle,int tail){
int indexFirst=head;
int indexHelp=head;
int indexNext=middle+1;
//2个数组都还有元素
while(indexFirst<=middle&&indexNext<=tail){
if(arr[indexFirst]<arr[indexNext]){
help[indexHelp++]=arr[indexFirst++];
}else{
help[indexHelp++]=arr[indexNext++];
}
}
//如果第一个数组还有剩余
while(indexFirst<=middle){
help[indexHelp++]=arr[indexFirst++];
}
//如果第二个数组还有剩余
while(indexNext<=tail){
help[indexHelp++]=arr[indexNext++];
}
//写回到原数组
for(int i=head;i<=tail;i++){
arr[i]=help[i];
}
}
