文章目录
基础排序算法O(n^2)选择排序插入排序及优化冒泡排序及优化希尔排序及优化 高级排序算法O(nlogn)归并排序及优化快速排序及优化堆和堆排序排序算法总结本文为慕课网实战课程《算法与数据结构》学习笔记
基础排序算法O(n^2)
选择排序
在剩下未排序的数里选择最小的排序
i向前，j在i+1~n内比较
时间复杂度 O ( n 2 ) O(n^2) O(n2)
public static void sort(Comparable[] arr){int n = arr.length;for( int i = 0 ; i < n ; i ++ ){// 寻找[i, n)区间里的最小值的索引int minIndex = i;for( int j = i + 1 ; j < n ; j ++ )if( arr[j].compareTo( arr[minIndex] ) < 0 )minIndex = j;swap( arr , i , minIndex);}}
插入排序及优化
类似扑克摸牌插牌过程，新数与之前的数比较
i每次往前，j向后(backward)比较
public static void sort(Comparable[] arr){int n=arr.length;for (int i = 1; i < n ; i++) {// j与j-1相比，向后比较for(int j=i;j>0; j--) {if (arr[j].compareTo(arr[j-1]) < 0)sort.swap( arr , j , j-1);elsebreak;}}}
优化1：减少交换次数
记录i，比j大的右移
public static void sort(Comparable[] arr){int n=arr.length;for (int i = 1; i < n ; i++) {// 保存当前副本Comparable temp=arr[i];// 只交换1次，其余赋值int j;for( j = i; j > 0 && arr[j-1].compareTo(temp)>0 ; j--) {arr[i]=arr[j-1];}arr[j]=temp;}}
优化2：记录最大最小值，减少比较次数
分成左右两部分及记录最大最小值
左右窗口渐渐缩小
public static void sort(Comparable[] arr){int left = 0, right = arr.length - 1;while(left < right){int minIndex = left;int maxIndex = right;// 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]if(arr[minIndex].compareTo(arr[maxIndex]) > 0)sort.swap(arr, minIndex, maxIndex);//i向右移动，时刻比较与最大最小值的比较大小for(int i = left + 1 ; i < right; i ++) {if (arr[i].compareTo(arr[minIndex]) < 0)minIndex = i;else if (arr[i].compareTo(arr[maxIndex]) > 0)maxIndex = i;}sort.swap(arr, left, minIndex);sort.swap(arr, right, maxIndex);left ++;right --;}}
冒泡排序及优化
每一次循环中最大的放末位。窗口缩小
public static void sort(Comparable[] arr){int n =arr.length;//边界问题for (int i = 0; i < n-1 ; i++) {for (int j = 0; j < n-i-1 ;j++){if(arr[j].compareTo(arr[j+1])>0)sort.swap(arr,j,j+1);}}
优化：改进循环
//优化了npublic static void sort(Comparable[] arr){int n =arr.length;boolean swap=false;do {for (int i = 1; i < n - 1; i++) {if (arr[i - 1].compareTo(arr[i]) > 0) {sort.swap(arr, i - 1, i);swap=true;}}n--;}while (swap);}
希尔排序及优化
分组（[i]与[i+h]、[i+2h]…为一组）、有增量(h)的插排。增量递减，为1时停止。
public static void sort(Comparable[] arr){int n=arr.length;int gap=2;//增量的比例int h=1;while (h<n/gap)h=gap*h+1;while(h>0) {for (int i = h; i < n; i++) {// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序for (int j = i; j >= h; j = j - h) {// 最右端往前比较if (arr[j].compareTo(arr[j - h]) < 0)sort.swap(arr, j, j - h);}}h = h / gap;}}
高级排序算法O(nlogn)
归并排序及优化
自顶向下，一分为二，递归分化为小段，小段排序，共有logn层 合并。。。
public static void merge(Comparable[] arr,int l,int mid,int r) {Comparable[] temp = Arrays.copyOfRange(arr, l, r + 1);//temp[0]~temp[r-l+1]int i = l;int j = mid + 1;for (int k=l;k<=r;k++){//l~r 映射到0~r-l+1// 当左右部分元素处理完 [l,i,mid][mid+1,j,r]if( i > mid ){// 如果左半部分元素已经全部处理完毕arr[k] = temp[j-l]; j ++;}else if( j > r ){// 如果右半部分元素已经全部处理完毕arr[k] = temp[i-l]; i ++;}// 当左右部分还有元素可处理else if( temp[i-l].compareTo(temp[j-l]) < 0 ){// 左半部分所指元素 < 右半部分所指元素arr[k] = temp[i-l]; i ++;}else {arr[k] = temp[j-l]; j++;}}}// 递归使用归并排序,对arr[l...r]的范围进行排序private static void sort(Comparable[] arr, int l, int r) {// if (l >= r)// return;// 优化2：递归到数量级比较小的时候跳转插入排序。插入排序在小数量级排序更有优势if(r-l<= 15)//16个元素的时候{insertSort.sort(arr,l,r);return;}int mid = (l+r)/2;sort(arr, l, mid);sort(arr, mid + 1, r);if(arr[mid].compareTo(arr[mid+1])>0)//优化1，当左边最大>右边最小时才需要合并merge(arr, l, mid, r);}//第一次sortpublic static void sort(Comparable[] arr){int n = arr.length;sort(arr, 0, n-1);}
自底向上的归并排序
// 与自顶向下相比 对链表友好 nlognpublic static void mergeSortBU(Comparable[] arr){int n=arr.length;for (int gap = 1; gap <= n; gap += gap) {for (int i = 0; i < n-gap ; i=1+ 2*gap) {//每次merge的左右部分[i...i+gap-1],[i+gap,...i+2gap-1]，i+gap<n 保证左边组完整即可mergeSort.merge(arr,i,i+gap-1, Math.min(i+2*gap-1,n-1));//数组可能越界。右边部分数量选择}}}
快速排序及优化
选取第一位的数v为标准其他数与其比较，小于它的放到j位置，大于的不操作。最后把v放到j处。
public static void sort(Comparable[] arr){int n=arr.length;sort(arr,0,n-1);}public static void sort(Comparable[] arr,int l,int r){if(l>=r)return;// 优化1：也可化成插入排序int p= partition(arr,l,r);//p值是取排在第一个的数，最后放入正确位置sort(arr,l,p-1);sort(arr,p+1,r);}//返回p使得arr[l...p-1]<arr[p]<arr[p+1...r]public static int partition(Comparable[] arr,int l,int r) {Comparable v=arr[l];// arr[l+1,...j]< v v>arr[j+1,...i)int j=l;for (int i = l+1; i <= r ; i++) {if (arr[i].compareTo(v)< 0) {sort.sort.swap(arr, i, j + 1);j++;}}sort.sort.swap(arr,l,j);return j;}
当近乎有序的数组快排慢于归并排序。因为一分为二的两边长短不一，生成的递归树平衡度差。最差情况(完全有序数组)退化为0(n^2)。改为随机选择 v
public static int partition(Comparable[] arr,int l,int r) {// arr[l+1,...j]< v v>arr[j+1,...i)int j=l;// (l,r) 随机选择分割点int rand=((int)Math.random()*(r-l+1)+l);Comparable v=arr[rand];// sort.sort.swap( arr, l , rand); // Comparable v=arr[l]; 把标记点放在首位，便于画图，这里为了减少一次交换则将v直接赋值randfor (int i = l+1; i <= r ; i++) {if (arr[i].compareTo(v)< 0) {sort.sort.swap(arr, i, j + 1);j++;}}sort.sort.swap(arr,l,j);return j;}
优化1：双路快速排序
当随机数组range小则e=v的情况太多。无论将e=v划分到＜组还是＞组，数组都不平衡。解决思路1，把=情况分散到＜和＞组。
public static int partition2(Comparable[] arr ,int l,int r){Comparable v = arr[l];int i=l+1;int j=r;// arr[l+1,...j)<= varr(j,...r]>=vdo{// 若使用<= i会吸收所有的 =v 在此逻辑上会导致树不平衡。while(i<=r&&arr[i].compareTo(v) < 0) i++;while(j>=l+1&&arr[j].compareTo(v)> 0) j--;if(i>j)break;// 当arr[i]>=v || arr[j]<=vsort.sort.swap(arr,i,j);i++;j--;}while(true);sort.sort.swap(arr,l,j);return j;}
优化1：三路快速排序
public static void sort(Comparable[] arr, int l, int r){// 对于小规模数组, 使用插入排序，删除可能栈内存溢出if( r - l <= 15 ){insertSort.sort(arr, l, r);return;}// 随机在arr[l...r]的范围中, 选择一个数值作为标定点sort.sort.swap( arr, l, (int)(Math.random()*(r-l+1)) + l );Comparable v = arr[l];// 初始值要数组为空int lt = l;// arr[l+1...lt] < vint gt = r + 1; // arr[gt...r] > vint i = l+1; // arr[lt+1...i) == vwhile(i < gt ) {if(arr[i].compareTo(v)<0) {sort.sort.swap(arr,i,lt+1);i++;lt++;}else if(arr[i].compareTo(v)>0){sort.sort.swap(arr,i,gt-1);gt--;//此时i仍指向的未处理的元素,也因此不用for循环}else {i++;}}sort.sort.swap( arr, l, lt );sort(arr, l, lt-1);sort(arr, gt, r);}public static void sort(Comparable[] arr){int n=arr.length;sort(arr,0,n-1);}
归并排序和快速排序总结：
都使用分治算法，一个侧重处理“合”部分，一个侧重“分”部分
堆和堆排序
实际中优先队列这个概念应用广泛，任务出队与优先级有关而与入队顺序无关。使用二叉堆实现这一概念。最大堆是越大值在顶端的二叉堆，是完全二叉树（父节点>子节点，除了叶子节点外其它层节点的个数最大，叶子节点都在左子树）。
使用数组存储最大堆
public class MaxHeap<Item extends Comparable> {protected Item[] data;protected int count;protected int capacity;// 构造函数, 构造一个空堆, 可容纳capacity个元素public MaxHeap(int capacity){data = (Item[])new Comparable[capacity+1];count = 0;this.capacity=capacity;}public int size(){return count;}public boolean isEmpty(){return count ==0;}public void swap(int i,int j){Item t=data[i];data[i]=data[j];data[j]=t;}}
向堆中加入数据：数组末尾增加数据，再调整树保证其最大堆属性
public void insert(Item item){// 确保不越界assert count+1<=capacity;// 数组是从1开始记录data[count+1]=item;count++;shiftUp(count);}// 判断与父节点的大小public void shiftUp(int k){// 比父节点大，则交换，往上比较while(k>1&& data[k].compareTo(data[k/2])>0) {swap(k,k/2);k/=2;}}
取出堆中最大值： 取出data[1],把末尾数值填入最大位置，再调整树
// 提出1 头节点，最后一位放到1位置，再shiftDown调整树public Item takeMax(){// 堆不为空assert count>1;Item ret =data[1];swap(1,count);count--;shiftDown(1);return ret;}// 获取最大堆中的堆顶元素public Item getMax(){assert( count > 0 );return data[1];}public void shiftDown(int k){//保证有左孩子while (2*k<=count){int j=2*k; //子节点if (j+1<=count&& data[j+1].compareTo(data[j])>0)j++;//此时j是孩子中大的那个节点(保证交换后的父节点比子节点都大)// k比孩子节点都大，满足最大堆条件，跳出if(data[k].compareTo(data[j])>=0)break;swap(k,j);k=j;//循环 }}
此时可以通过循环取出最大值对数组进行排序。
优化1：heapify数组转化成堆
public MaxHeap(Item[] arr){int n=arr.length;this.capacity=n;data = (Item[])new Comparable[n+1];for (int i = 0; i <n ; i++) {data[i+1]=arr[i];}this.count=n;// heapify操作 count/2为第一个非叶子节点for (int i = count/2; i >=1 ; i--) {shiftDown(i);}}public static void sort(Comparable[] arr){int n=arr.length;MaxHeap<Comparable> heap=new MaxHeap<>(arr);for (int i = n-1; i >0 ; i--) {arr[i]=heap.takeMax();}}
优化2：原地堆排序
优化1还要多开辟内存空间给堆。原地堆在数组上改造成堆。取出最大值放在数组末尾，对剩下的数组[0,n-1-1] 重新整理成最大堆，迭代。最后完成排序
此时堆从0开始 [0,n-1], 第一个非叶子节点为(n-1-1)/2
// 赋值代替swappublic static void shiftDown2(Comparable[] arr, int n,int k){Comparable e=arr[k];//保证有左孩子while (2*k+1<=n){int j=2*k+1; //子左节点if (j+1< n&& arr[j+1].compareTo(arr[j])>0)j++;//此时j是大的那个节点(保证交换后的父节点比子节点都大)if(pareTo(arr[j])>=0)break;arr[k]=arr[j];k=j;}arr[k]=e;}public static void sort(Comparable[] arr){int n=arr.length;// heapify把数组原地做成最大堆// n-1-1是第一个非叶子节点的左孩子 (n-1-1)/2是第一个非叶子结点for (int i = (n-1-1)/2; i >=0 ; i--) {shiftDown2(arr,n,i);}//排序for (int i = n-1; i >0 ; i--) {sort.sort.swap(arr,0,i);shiftDown2(arr,i,0);}}
索引堆及其优化
假设data是进程的优先级，若需要修改某个进程的优先级则最大堆很难追踪原数据。其次，交换data位置消耗性能，若data为长string类，耗损较大。若单单在类中加入index记录原data位置，则需要遍历整个数组找到。 因此引入索引堆。
index数组做成堆，而不是data。解释为：index记录data的位置，堆中第i个元素实际数据是data[ index[i] ] 举例🌰：index[1]=10=data[10]=62 即堆顶数据为62
逻辑与上面相同，只不过比较的时候是data[index[i]]实际交换的是index[i]
public class indexMaxHeap01<Item extends Comparable> extends MaxHeap {protected Item[] data;protected int count;protected int capacity;protected Integer[] index;public indexMaxHeap01(int capacity){this.capacity=capacity;data = (Item[])new Comparable[capacity+1];index=new Integer[capacity+1];this.count=0;}private void swapindex(int i, int j) {int t = index[i];index[i] = index[j];index[j] = t;}public void insert(int i, Item item){assert count + 1 <= capacity;assert i + 1 >= 1 && i + 1 <= capacity;i += 1;data[i] = item;index[count+1] = i;count ++;shiftUp(count);}@Overridepublic void shiftUp(int k) {// 比较data 交换indexwhile(k>1&& data[index[k]].compareTo(data[index[k/2]])>0) {swapindex(k,k/2);k/=2;}}@Overridepublic Item takeMax() {assert count>0;Item ret =data[index[1]];swapindex(1,count);count--;shiftDown(1);return ret;}@Overridepublic void shiftDown(int k){//保证有左孩子while (2*k<=count){int j=2*k; //子节点if (j+1<=count&& data[index[j+1]].compareTo(data[index[j]])>0)j++;//此时j是大的那个节点(保证交换后的父节点比子节点都大)if(data[index[k]].compareTo(data[index[j]])>=0)break;swapindex(k,j);k=j;}}public int takeMaxindex() {assert count>1;int ret =index[1]-1;swapindex(1,count);count--;shiftDown(1);return ret;}public Item getItem(int i){return data[i+1];}// 通过索引堆修改data内容// nlogn+n = O(n)public void change(int i, Item newItem){i+=1;data[i]=newItem;// 找到index[j]=i j表示data[i]在堆中的位置// 之后shiftup(j),再shiftdown(j)for (int j = 1; j <=count ; j++) {if(index[j]==i){shiftUp(j);shiftDown(j);return;}}}public static void main(String[] args) {int N=10;indexMaxHeap<Integer> heap=new indexMaxHeap<>(10);// Integer[] arr = TestHelper.generateRandomArray(N, 0, 10);Integer[] test={15,17,19,13,22,16,28,30,41,62};for (int i = 0; i < N ; i++) {heap.insert(i,test[i]);}System.out.printf("i : ");for (int i = 1; i <= N ; i++) {System.out.printf(i+" ");}System.out.println();System.out.printf("data: ");for (int i = 0; i <N ; i++) {System.out.printf(heap.getItem(i)+" ");}System.out.println();System.out.printf("sort: ");for (int i = 0; i <N ; i++) {System.out.printf(heap.takeMax()+" ");}}}
优化: 增加reverse属性帮助查找
如上面所述，索引最大堆若需要改动data[4]的值，再去更新index。则需要遍历一遍直到index[i]=4.此时复杂度O(n)，为了改进，引入rev(reverse)反向查找 ,记录index的位置rev[i]=j ；index[j]=1 ； rev[index[i]]=i ; index[rev[j]]=j则更新index =更新index[rev[4]]即可。
public class indexMaxHeap<Item extends Comparable> extends MaxHeap {protected Item[] data;protected int count;protected int capacity;protected Integer[] index;protected Integer[] rev;public indexMaxHeap(int capacity){this.capacity=capacity;data = (Item[])new Comparable[capacity+1];index=new Integer[capacity+1];rev=new Integer[capacity+1];for (int i = 0; i <=capacity; i++) {rev[i] = 0;}this.count=0;}private void swapindex(int i, int j){int t = index[i];index[i] = index[j];index[j] = t;rev[index[i]] = i;rev[index[j]] = j;}// 传入的i对用户而言是从0开始的public void insert(int i, Item item){assert count + 1 <= capacity;assert i + 1 >= 1 && i + 1 <= capacity;// 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。assert !contain(i);i += 1;data[i] = item;index[count+1] = i;rev[i] = count + 1;count ++;shiftUp(count);}@Overridepublic void shiftUp(int k) {不变}@Overridepublic Item pushMax() {assert count>0;Item ret =data[index[1]];swapindex(1,count);rev[index[count]]=0;//删除末尾 即置为0count--;shiftDown(1);return ret;}@Overridepublic void shiftDown(int k){不变}public int pushMaxindex() {assert count>1;int ret =index[1]-1;swapindex(1,count);rev[index[count]] = 0;count--;shiftDown(1);return ret;}//索引i存在在堆中public boolean contain(int i){assert (i>=0 && i<=capacity);return rev[i+1] !=0;}public Item getItem(int i){assert(contain(i));return data[i+1];}// 通过索引堆修改data内容// nlogn+n = O(n)public void change(int i, Item newItem){assert(contain(i));i+=1;data[i]=newItem;shiftUp(rev[i]);shiftDown(rev[i]);}}
