Contents
  1. 1. 游标因子的设置
  2. 2. 排序原理
  3. 3. 复杂度
    1. 3.1. 空间复杂度:
    2. 3.2. 时间复杂度
  4. 4. 算法实现的注意事项
    1. 4.1. 插入排序代码实现
    2. 4.2. 希尔排序代码实现
    3. 4.3. 快排的代码实现
    4. 4.4. 堆排序的代码实现
    5. 4.5. 归并排序的代码实现
  5. 5. 优先队列
  6. 6. 代码
    1. 6.1. 选择排序
    2. 6.2. 插入排序
    3. 6.3. Shell
    4. 6.4. Quick
    5. 6.5. heap
    6. 6.6. Merge

手写一套经典的所有排序算法源码
https://github.com/huangzhenshi/ClassicSort/tree/master

游标因子的设置

  • 选择排序需要一个游标,int index=0,标志该轮比较当中,最大值所在的下标位置
  • 插入排序需要一个游标,int index=j,如果后面元素比前面元素小,则交换之后游标向前游动
  • 希尔排序需要一个游标,类似于插入排序,只是游标左游的长度为d
  • 快速排序需要两个游标,除了 low high这种原始标志位,还需要head标识前置哨兵目前所在的位置和tail标识数组后置哨兵所在的位置(last哨兵后面的都比arr[index]大)
  • 堆排序需要一个游标,来标志末位元素的位置
  • 归并排序需要三个游标,除了 low mid high ,还需要 i j k,来实现比较拷贝

排序原理

  • 选择:遍历比较数组最大值,通过游标标记,最后和末位交换。2个for循环和index解决问题。
  • 冒泡:遍历比较最大值,不停交换最大值一直到末位,2个for循环解决问题。
  • 插入:维护一个递增的数组,通过一个游标,和最大的数比,比最大的大就break;否则游标和比较对象都左移
  • 希尔:3层for循环+while,插入排序的改进版本,跨度插入排序形成基本有序数组再插入排

  • 快排:每次首位元素通过交换找到它在该数组段中的位置,再递归,引入low high head tail关键标记位。基于这种思路,可以解决无序数组中中位数,和无需数组求中位数的算法,随机第一个元素切分数组,缩小范围的方式来定位查找目标。

  • 归并(分治):精华是拆分问题,把数组拆分成2个小数组最后在递归性的从小问题解决到最大的问题,第二个核心在于2个连续的有序数组的merge方法。利用一个辅助数组。

复杂度

空间复杂度:

  • 一般的排序都是平均的空间复杂度都是O(1),只需要支付 exchange(int start,int end,int[] arr)时的成本,最佳就是本来有序O(0)
  • 归并排序依赖一个辅助的数据,空间复杂度为 O(N)
  • 快排的依赖是递归,O(logN)

时间复杂度

  1. 快排
  • 最佳的时间复杂度 NlogN,最差 N平方,平均NlogN
  • 最佳是每次都是中位,递归长度减半,logN次均分,最差是数组正序或者逆序
  • 解决最差情况:哨兵排之前做一次随机取值,再交换的处理。
  • 改进方法2:N<47时用插入,提速

算法实现的注意事项

  • 选择、冒泡、插入两个for循环,所以时间复杂度为N平方
  • 希尔排序:4层for循环2个因素基本上
  • 快排:递归套一层while循环判断tail和head是否碰头

插入排序代码实现

  • 两层for循环(或者一个for循环+while)
  • 需要一个关键游标 index,每次左移的时候,比较对象也要一起移动
  • 比较大小的时候,大于则break;小于则交换且游标和比较对象一起左移

希尔排序代码实现

  • 四层for循环,2层用于快排、1层用于i=0 i0
  • 需要两个关键游标 d和index

快排的代码实现

  • 一个locate,一个while
  • 2个游标:head、tail;2个判断 high<=low return,while(tail>head)

堆排序的代码实现

  • 写MaxPQ,size,sink(),swim()
  • 构建有序堆(N/2开始依次sink())
  • for循环,交换末位,setSize(–tail),sink(1)

归并排序的代码实现

  • 拆分问题,start<end时,求mid,拆分2个问题,merge
  • 归并方法:3个游标、一个辅助数据、3层while一层for,写入又写会arr1数组当中

优先队列

  • 解决的问题:构建一个有序堆,堆顶的元素最大,且重新插入一个元素,或者删除堆顶元素,堆重构的代价并不大。用于堆排序,或者查找最值的业务场景中
  • N指的是list.size()-1,数组首位为null
  • swim() ,有序堆从末位追加一个元素,调用swim()方法,重建堆有序,用于已经堆有序的堆中添加新元素
  • 构建优先队列的时候要控制size,因为最后排序的时候涉及到堆顶和数组末位交换位置实现排序功能
  • sink()的时候首先要判断是否有2个子节点,然后取最大的一个和父节点比较,不然会出错

代码

选择排序

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 start,int end,int[] arr){
if(start>=end) return;
int index=start;
int last=end;
while(last>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, last, arr);
last--;
}
}
locate(start,index-1,arr);
locate(index+1,end,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];
}
}
Contents
  1. 1. 游标因子的设置
  2. 2. 排序原理
  3. 3. 复杂度
    1. 3.1. 空间复杂度:
    2. 3.2. 时间复杂度
  4. 4. 算法实现的注意事项
    1. 4.1. 插入排序代码实现
    2. 4.2. 希尔排序代码实现
    3. 4.3. 快排的代码实现
    4. 4.4. 堆排序的代码实现
    5. 4.5. 归并排序的代码实现
  5. 5. 优先队列
  6. 6. 代码
    1. 6.1. 选择排序
    2. 6.2. 插入排序
    3. 6.3. Shell
    4. 6.4. Quick
    5. 6.5. heap
    6. 6.6. Merge