概述
- 排序原理
- 选择排序：遍历比较数组最大值，通过游标标记，最后和末位交换。2个for循环和index解决问题。
- 冒泡排序：遍历比较最大值，不停交换最大值一直到末位，2个for循环解决问题。
- 插入排序：维护一个递增的数组，通过一个游标，和最大的数比，比最大的大就break；否则游标和比较对象都左移
- 希尔排序：3层for循环+while，插入排序的改进版本，跨度插入排序形成基本有序数组再插入排
- 快排排序：每次首位元素通过交换找到它在该数组段中的位置，再递归，引入low high head tail关键标记位。基于这种思路，可以解决无序数组中中位数，和无需数组求中位数的算法，随机第一个元素切分数组，缩小范围的方式来定位查找目标。
- 归并(分治)：精华是拆分问题，把数组拆分成2个小数组最后在递归性的从小问题解决到最大的问题，第二个核心在于2个连续的有序数组的merge方法。利用一个辅助数组。
- 堆排序：初始化的时候构建最大堆（调用 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;
for(int j=i-1;j>=0;j--){
if(arr[index]>arr[j]) break;
Util.exchange(index, j, 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 static void locate(int low,int high,int[] arr){
if(low>=high) return;
int index=low;
int tail=high;
while(tail>index){
if(arr[index]>arr[index+1]){
Util.exchange(index, index+1, arr);
index++;
}else if(arr[index]<arr[index+1]){
Util.exchange(index+1, tail, arr);
tail--;
}
}
locate(low,index-1,arr);
locate(index+1,high,arr);
}
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
//对一个数组按照下标进行归并排序
//归并排序的精华所在：问题拆分，把一个大问题拆分为N个性质一样但更简单的小问题
public static void mergeSort(int[] arr,int start,int end){
//这也是递归的终结，当数组拆分到只有1个元素的时候，必然是有序的，否则就继续拆分
if(start<end){
//拆分大问题为两个小问题
int mid=(start+end)/2;
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
//小问题解决完之后，最后父问题
merge(arr,start,mid,end);
}
}
//有两个数组，一个数源数组arr1，一个是工具数组是长度一样但是都是null的arr2
//arr1数组中有2个连续且有序的数组 arr11 和 arr12
//low是arr11的start，mid是arr11的end，mid+1是arr12的start，high是arr12的end
//设置了3个游标，i为arr11的游标，j为arr12的游标，k为arr2的游标
//merge的思路是当arr11和arr12中从起始位置开始比较，最小的写到arr2中，一直到有一个掏空了
//假如是arr11先掏空，那么顺序把arr12中的元素顺序写入到arr2中；反之把arr11中剩余元素写入到arr2中
//最后再把工具数组里的数据按照low high位置写回到arr1中，这样可以arr1可以继续比较了
public static int[] arr2=new int[20];
public static void merge(int[] arr1,int low,int mid,int high){
int i=low,k=low,j=mid+1;
//当arr11和arr12中从起始位置开始比较，最小的写到arr2中，对应下标移动，一直到有一个掏空了为止
while(i<=mid&&j<=high){
if(arr1[i]<arr1[j]){
arr2[k++]=arr1[i++];
}else {
arr2[k++]=arr1[j++];}
}
//如果是arr12先被掏空，则arr11中剩余元素写入到arr2中,这里可以优化
while(i<=mid){
arr2[k++]=arr1[i++];
}
//如果是arr11先被掏空，则arr12中剩余元素写入到arr2中，这里可以优化
while(j<=high){
arr2[k++]=arr1[j++];
}
//arr2排序结束写回到arr1中相应位置
for (i = low; i <= high; i++) {
arr1[i] = arr2[i];
}
}
网友评论