精华内容
下载资源
问答
  • 直接插入排序(插入排序) 排序思想 对于一个数组 A[0,n] 的排序问题,假设认为数组在 A[0,n-1] 排序的问题已经解决了。 考虑 A[n] 的值,从右向左扫描有序数组 A[0,n-1] ,直到第一个小于等于 A[n] 的元素,将 A[n] ...

    直接插入排序(插入排序)

    排序思想

    • 对于一个数组 A[0,n] 的排序问题,假设认为数组在 A[0,n-1] 排序的问题已经解决了。
    • 考虑 A[n] 的值,从右向左扫描有序数组 A[0,n-1] ,直到第一个小于等于 A[n] 的元素,将 A[n] 插在这个元素的后面。

    在这里插入图片描述

    插入排序运用时需要注意的

    直接插入排序对于 最坏的情况(严格递减/递增的数组),需要比较和移位的次数为 n(n-1)/2

    对于 最好的情况(严格递增/递减的数组),需要比较的次数是 n-1 ,需要移位的次数是 0

    直接插入排序适用于 顺序存储链式存储结构 的线性表。注意,为链式存储时,可以从前往后查找指定元素的位置。一般来说,当 数据规模较小 的情况下,可以考虑使用直接插入排序

    插入排序算法分析

    直接插入排序的时间复杂度是 O(n^2),空间复杂度是 O(1),同时也是 稳定排序

    稳定排序:待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj(即i<j).若在排序后的序列中Ri仍然领先于Rj,则称所用的方法是稳定的。

    比如int数组[1,1,1,6,4]中a[0],a[1],a[2]的值相等,在排序时不改变其序列,则称所用的方法是稳定的。

    代码实现

    class Solution{
    public:
    	void insertSortion(vector<int> &nums) {
    		if(nums.size() < 2) return;
    		for(int i = 1; i < nums.size(); i++) {
    			int num = nums[i];
    			// 防止插入的数是最小的 
    			bool flag = false;
    			// for循环中,若插入值是最小的,没有给最小的值安排位置 
    			for(int j = i - 1; j > -1; j--) {
    				if(nums[j] > num) {
    					nums[j+1] = nums[j];
    				} else {
    					nums[j+1] = num;
    					flag = true;
    					break;
    				}
    			}
    			if(!flag) {
    				nums[0] = num; 
    			}
    		}
    		return;
    	} 
    };
    

    加工后执行的结果

    在这里插入图片描述

    折半插入排序(插入排序)

    排序思想:折半插入排序的改进版

    1. 有一组数列待排序,排序区间为 Array[0, n-1] 。将数列分为有序数列和无序数列,第一次排序时默认 Array[0] 为有序数列,Array[1, n-1] 为无序数列。有序数列分区的第一个元素位置为 low ,最后一个元素的位置为 high
    2. Array[0, i-1] 为有序数列,待插入数据为 Array[i]。由于 Array[0, i-1] 有序,使用对有序数列的查找,最好的方法时时间复杂度为 O(logn) 的折半查找,通过折半查找找到插入位置(即 low > high 时),将该位置及之后的数据分别往后挪一位

    在这里插入图片描述

    折半插入排序运用时需要注意的条件和直接插入排序时需注意的条件一样

    折半插入排序对于 最坏的情况(严格递减/递增的数组),需要比较和移位的次数为 n(n-1)/2

    对于 最好的情况(严格递增/递减的数组),需要比较的次数是 n-1 ,需要移位的次数是 0

    但相比直接插入排序,折半插入排序在 查找位置的时候得到优化(O(n)O(logn)

    折半排序算法分析

    折半插入排序的时间复杂度是 O(n^2),空间复杂度是O(1),同时也是 稳定排序

    代码实现

    #include <stdio.h> 
    #include <vector>
    using namespace std;
    class Solution{
    public:
    	void binaryInsertionSort(vector<int> &nums) {
    		if(nums.size() < 2) return;
    		for(int i = 1; i < nums.size(); i++) {
    			int low = 0;
    			int high = i;
    			int num = nums[i];
    			while(low <= high) {
    				int mid = (low + high) / 2;
    				if(nums[mid] > num) {
    					high = mid - 1;
    				} else {
    					low = mid + 1;
    				}
    			}
    			int j;
    			for(j = i - 1; j > high; j--) {
    				nums[j+1] = nums[j];
    			}
    			nums[j+1] = num; 
    		}
    		return; 
    	} 
    };
    

    加工后执行的结果

    在这里插入图片描述

    希尔排序(插入排序)

    排序思想:通过粗调的方式减少了直接插入排序的工作量

    对于 Array[0,n-1] 这个数列有 n 个待排序的数字,取一个小于 n 的整数 stepstep被称为步长)将待排序元素分成若干个组子序列,所有距离为 step 的倍数的记录放在同一个组中;然后,对各组内的元素进行直接插入排序。 这一趟排序完成之后,每一个组的元素都是有序的。然后减小 step 的值,并重复执行上述的分组和排序。重复这样的操作,当 step=1 时,整个数列就是有序的。

    在这里插入图片描述

    希尔排序

    希尔排序的时间复杂度与增量(即,步长 step )的选取有关。例如,当增量 step 为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为 O(n²)

    遇到极端情况,比如 step=4step=2 时,数组序列不变,进入 step=1 时,就是直接插入排序了,相比正常的直接插入排序,还多加了几次 step=4step=2 的判断

    希尔排序仅适用于线性表为顺序存储的情况。

    希尔排序算法分析

    希尔插入排序的时间复杂度是 O(n^2),空间复杂度是 O(1) ,但希尔排序是 不稳定排序

    代码实现

    class Solution{
    public:
    	void ShellSort(vector<int> &nums) {
    		int size = nums.size();
    		int count = 0;
    		for(int step = size / 2; step > 0; step /= 2) {
    			for(int i = 0; i < step; i++) {
    				insertSort(nums, size, i, step);
    			}
    		}
    	} 
    private:
    	void insertSort(vector<int> &nums, int size, int i, int step){
    		for(int j = i + step; j < size; j+=step) {
    			if(nums[j] < nums[j-step]) {
    				int num = nums[j];
    				int k = j - step;
    				while(k >= 0 && nums[k] > num) {
    					nums[k+step] = nums[k];
    					k -= step;
    				}
    				nums[k+step] = num;
    			}
    		}
    		return;
    	}
    };
    

    加工后执行的结果
    在这里插入图片描述

    完整测试代码

    直接插入排序测试代码

    #include <stdio.h>
    #include <vector>
    using namespace std;
    class Solution{
    public:
    	void insertSortion(vector<int> &nums) {
    		if(nums.size() < 2) return;
    		printf("第0轮:");
    		for(int i = 0; i < nums.size(); i++) {
    			printf("%d",nums[i]);
    			if(i!=nums.size()-1) printf(",");
    		}
    		printf("\n");
    		for(int i = 1; i < nums.size(); i++) {
    			int num = nums[i];
    			// 防止插入的数是最小的 
    			bool flag = false;
    			// for循环中,若插入值是最小的,没有给最小的值安排位置 
    			for(int j = i - 1; j > -1; j--) {
    				if(nums[j] > num) {
    					nums[j+1] = nums[j];
    				} else {
    					nums[j+1] = num;
    					flag = true;
    					break;
    				}
    			}
    			if(!flag) {
    				nums[0] = num; 
    			}
    			// 查看 
    			printf("第%d轮:",i);
    			for(int i = 0; i < nums.size(); i++) {
    				printf("%d",nums[i]);
    				if(i!=nums.size()-1) printf(",");
    			}
    			printf("\n");
    		}
    		return;
    		
    	} 
    };
    
    int main() {
    	vector<int> v;
    	v.push_back(23);
    	v.push_back(76);
    	v.push_back(34);
    	v.push_back(89);
    	v.push_back(90);
    	v.push_back(34);
    	v.push_back(56);
    	v.push_back(18);
    	Solution solution;
    	solution.insertSortion(v);
    	return 0;
    }
    

    折半插入排序测试代码

    #include <stdio.h> 
    #include <vector>
    using namespace std;
    class Solution{
    public:
    	void binaryInsertionSort(vector<int> &nums) {
    		if(nums.size() < 2) return;
    		printf("第0轮:");
    		for(int i = 0; i < nums.size(); i++) {
    			printf("%d",nums[i]);
    			if(i!=nums.size()-1) printf(",");
    		}
    		printf("\n");
    		for(int i = 1; i < nums.size(); i++) {
    			int low = 0;
    			int high = i;
    			int num = nums[i];
    			while(low <= high) {
    				int mid = (low + high) / 2;
    				if(nums[mid] > num) {
    					high = mid - 1;
    				} else {
    					low = mid + 1;
    				}
    			}
    			int j;
    			for(j = i - 1; j > high; j--) {
    				nums[j+1] = nums[j];
    			}
    			nums[j+1] = num; 
    			// 查看 
    			printf("第%d轮:",i);
    			for(int i = 0; i < nums.size(); i++) {
    				printf("%d",nums[i]);
    				if(i!=nums.size()-1) printf(",");
    			}
    			printf("\n");
    		}
    		return; 
    	} 
    };
    
    int main() {
    	vector<int> v;
    	v.push_back(23);
    	v.push_back(76);
    	v.push_back(34);
    	v.push_back(89);
    	v.push_back(90);
    	v.push_back(34);
    	v.push_back(56);
    	v.push_back(18);
    	Solution solution;
    	solution.binaryInsertionSort(v);
    	return 0;
    }
    

    希尔排序测试代码

    #include <stdio.h>
    #include <vector>
    using namespace std;
    class Solution{
    public:
    	void ShellSort(vector<int> &nums) {
    		int size = nums.size();
    		int count = 0;
    		// 查看 
    		printf("第0轮:");
    		count++;
    		for(int i = 0; i < nums.size(); i++) {
    			printf("%d",nums[i]);
    			if(i!=nums.size()-1) printf(",");
    		}
    		printf("\n");
    		for(int step = size / 2; step > 0; step /= 2) {
    			for(int i = 0; i < step; i++) {
    				insertSort(nums, size, i, step);
    			}
    			// 查看 
    			printf("第%d轮:",count);
    			count++;
    			for(int i = 0; i < nums.size(); i++) {
    				printf("%d",nums[i]);
    				if(i!=nums.size()-1) printf(",");
    			}
    			printf("\n");
    		}
    	} 
    private:
    	void insertSort(vector<int> &nums, int size, int i, int step){
    		for(int j = i + step; j < size; j+=step) {
    			if(nums[j] < nums[j-step]) {
    				int num = nums[j];
    				int k = j - step;
    				while(k >= 0 && nums[k] > num) {
    					nums[k+step] = nums[k];
    					k -= step;
    				}
    				nums[k+step] = num;
    			}
    		}
    		return;
    	}
    };
    
    int main() {
    	vector<int> v;
    	v.push_back(23);
    	v.push_back(76);
    	v.push_back(34);
    	v.push_back(89);
    	v.push_back(90);
    	v.push_back(34);
    	v.push_back(56);
    	v.push_back(18);
    	Solution solution;
    	solution.ShellSort(v);
    	return 0;
    }
    

    所有的插入排序均不是全局有序(全局排序:即每一轮均有一个数字的位置不会改变)

    展开全文
  • 1. 思想  折半插入排序是对直接插入排序的改进。 直接插入排序就是不断的依次将元素插入...2.图解-折半查找    将关键字 7 折半查找插入到 numbersArray。 查找过程如上图 int[] numbersArray = {1,3...

    1. 思想

      折半插入排序是对直接插入排序的改进。 直接插入排序就是不断的依次将元素插入前面已经排好序的序列中。
      由于前半部分为已经排好的序列,这样就不用按顺序依次比较寻找插入点,而是采用折半查找的方法来加快寻找插入点

    2.图解-折半查找

     

      将关键字 7 折半查找插入到 numbersArray。 查找过程如上图

    
    int[] numbersArray = {1,3,4,6,7,8,10,13,14,18,19,21,24,37,40,45,71};
    
    //第 1 次
    low = 0
    high = 16
    middle = (0+16)/2 = 16/2 = 8
    7 (target at index 4) < 14 (middle at index 8)
    high = middle - 1 = 7
    
    //第 2 次
    low = 0
    high = 7
    middle = (0+7)/2 = 7/2 = 3 R 1
    7 (target at index 4) > 6 (middle at index 3)
    low = middle + 1 = 4
    
    //第 3 次
    low = 4
    high = 7
    middle = (4+7)/2 = 11/2 = 5 R 1
    7 (target at index 4) < 8 (middle at index 5)
    high = middle - 1 = 4
    
    //第 4 次
    low = 4
    high = 4
    middle = (4+4)/2 = 8/2 = 4
    7 (target at index 4) == 7 (middle at index 4)

    3.Code in Java

    import java.util.Arrays;
    
    class BinaryInsertionSort {
    
    	public static void main(String[] args) {
    		final int[] input = {4, 10, 3, 1, 9, 15, 40, 45, 71 };
    		System.out.println("Before Sorting - " + Arrays.toString(input));
    		new BinaryInsertionSort().sort(input);
    		System.out.println("After Sorting - " + Arrays.toString(input));
    	}
    
    	private static void sort(int[] dataArr) {
    		for (int i = 1; i < dataArr.length; i++) {
    			int temp = dataArr[i];
    			int low = 0, high = i - 1;
    			while (low <= high) {
    				int mid = (low + high) / 2;
    				if (temp < dataArr[mid]) {
    					high = mid - 1;
    				} else {
    					low = mid + 1;
    				}
    			}
    			int j = i - 1;
    			for (; j >= high + 1; j--) {
    				dataArr[j + 1] = dataArr[j];
    			}
    			dataArr[j + 1] = temp;
    		}
    	}
    
    
    
    }

    Code in C

    #include <stdio.h>
    #include <stdlib.h>
    
    
    
    // A binary search based function to find the position
    // where item should be inserted
    int binarySearch(int a[], int item, int low, int high)
    {
        if (high <= low)
            return (item > a[low])? (low + 1): low;
    
        int mid = (low + high)/2;
    
        if(item == a[mid])
            return mid+1;
    
        if(item > a[mid])
            return binarySearch(a, item, mid+1, high);
        return binarySearch(a, item, low, mid-1);
    }
    
    // Function to sort an array a[] of size 'n'
    void insertionSort(int a[], int n)
    {
        int i, loc, j, k, selected;
    
        for (i = 1; i < n; ++i)
        {
            j = i - 1;
            selected = a[i];
    
            // find location where selected sould be inseretd
            loc = binarySearch(a, selected, 0, j);
    
            // Move all elements after location to create space
            while (j >= loc)
            {
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = selected;
        }
    }
    
    // Driver program to test above function
    int main()
    {
        int a[] = {1, 18, 19, 21, 24, 37, 3, 4, 16, 7, 8, 10, 13, 40, 45};
        int n = sizeof(a)/sizeof(a[0]), i;
    
        insertionSort(a, n);
    
        printf("Sorted array: \n");
        for (i = 0; i < n; i++)
            printf("%d ",a[i]);
    
        return 0;
    }
    

     

     

     

    4.算法分析

      与直接排序比较:减少了关键字比较的次数,但记录移动的次数没有变,时间复杂度是 N²

    排序类别

    排序方法

    时间复杂度

    空间复杂度

    稳定性

    复杂性

    平均情况

    最坏情况

    最好情况

    插入排序

    折半插入排序

    O(N²)

    O(N²)

    O(N²)

    O(1)

    稳定

    简单

    5.参考

     

    https://en.wikipedia.org/wiki/Binary_search_algorithm

    展开全文
  • 2、折半插入排序跟直接插入排序大体思路是相同的,只不过查找的时候用的方式不一样,折半查找本质上只是较少了比较次数而已。代码如下: package com.paixuTest; import java.util.Arrays; /** * 折半插入排序 *...

    1、图解
    在这里插入图片描述
    2、折半插入排序跟直接插入排序大体思路是相同的,只不过查找的时候用的方式不一样,折半查找本质上只是较少了比较次数而已。代码如下:

    package com.paixuTest;
    
    import java.util.Arrays;
    
    /**
     * 折半插入排序
     *
     * 直接插入排序和折半插入排序大体思路是一样的,只不过在确定待排元素所要插入位置的方法用的不一样。
     * 直接插入排序,从后往前比较。
     * 折半插入排序是采用的折半查找法。
     * 两个都是在已经排好序的序列中进行查找。
     *
     * 查找、往后移动、插入
     *
     * 其实与直接插入排序的大体思路是一样的,只不过在查找位置的时候,不是从后往前挨着查找的,使用的是折半查找
     */
    public class zheBanChaRu {
    
        public static void main(String[] args) {
            int[] arr = new int[]{5,6,4,3,2,1,1,2,0,5,4,3};
            int temp = 0;
            int i,j;
            for (i=1;i<arr.length;i++){
                // 前后指针是动态变化的,跟前面有序序列长度相关
                int low = 0;
                int high = i-1;
                temp = arr[i];
                // 查找
                while (low<=high){
                    int mid = (low+high)/2;
                    if (temp>arr[mid]){
                        low = mid+1;
                    }else {
                        high = mid - 1;
                    }
                }
                // 确认了位置后移动元素  最终的位置就是low或者high+1
                for (j=i-1;j>=low;j--){  // 从后开始移动
                    arr[j+1] = arr[j];
                }
                // 将暂存元素插入到low或者high+1的位置
                arr[low] = temp;
            }
            // 输出数组
            System.out.println(Arrays.toString(arr));
    
        }
    }
    
    

    3、时间复杂度:最好 n 平均 nn 最坏nn
    稳定性:稳定的

    展开全文
  • 吃透排序 有个各类算法可视化的网站很不戳,对算法的执行过程不清晰地可以lou一眼,可以加深对算法的理解 网站地址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 以排序算法为例,点开网站找到...

    吃透排序

    更新ing,有错误欢迎提出讨论~

    一个网站

    有个各类算法可视化的网站很不戳,对算法的执行过程不清晰地可以lou一眼,可以加深对算法的理解
    网站地址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    以排序算法为例,点开网站找到排序模块
    在这里插入图片描述
    点击任何一个排序进入,然后就可以愉快看到各种排序的动画
    在这里插入图片描述

    排序基本概念

    思维导图

    先上思维导图
    在这里插入图片描述

    概念理解

    什么是算法的稳定性?
    文绉绉地说就是排序后,能使关键字相同的元素保持原来顺序中的相对位置不变
    如图就是相同的元素如两个3,排序后是否改变前后的相对位置
    在这里插入图片描述
    那稳定的排序算法一定优于不稳定的排序算法吗?
    nonono,如果算法对稳定性压根没要求,或者根本没有相同的元素,那稳定的排序算法也派不上什么用场了

    内部和外部排序有什么区别?
    内部排序:数据全部在内存
    外部排序:数据不全部在内存,有部分在外存
    在这里插入图片描述
    由于内存小,读写速度快,大约是外存(一般是硬盘)的600倍左右,所有内部排序我们更关注算法本身的优劣,即时间、空间复杂度

    由于外存大,读写速度慢(数据取出,拍好序再存回外存都需要进行磁盘的读写),所以外部排序我们更关注磁盘的读写的次数,这个次数越少越好

    插入排序

    思维导图

    在这里插入图片描述

    拆解排序过程

    插入排序又分为直接插入排序和折半插入排序
    第一个元素默认排好,后面元素一个个按序插入
    大致步骤就三步:
    1.找
    2.后移元素
    3.插入
    在这里插入图片描述

    直接插入排序

    上代码

      //直接插入排序
        void insertSort(int A[], int n) {
            int i, j, temp;//存放待排序元素
            for (i = 1; i < n; i++) {//从第二个元素开始插入排序
                if (A[i] < A[i - 1]) {
                    temp = A[i];
                    for (j = i - 1; j >= 0 && A[j] > temp; j--) {//元素后移
                        A[j + 1] = A[j];
                    }
                    A[j + 1] = temp//将待排序元素插入到正确的位置
                }
            }
    
        }
    
    

    在这里插入图片描述
    其实就是下图,需要j+1到正确的插入位置
    在这里插入图片描述
    还有一种带哨兵的直接插入排序的写法

    什么是哨兵?
    就是将数组A[0]的位置放放待排序的元素,然后整个数组的下标从1开始
    在这里插入图片描述

    上代码

     //    带哨兵的直接插入排序
        void insertSort1(int A[], int n) {
            int i, j;
            for (i = 2; i <= n; i++) {
                if (A[i] < A[i - 1]) {
                    A[0] = A[i];
                    for (j = i - 1; A[0] < A[j]; j--) {//元素后移
                        A[j + 1] = A[j];
                    }
                    A[j + 1] = A[0];//将待排序元素插入到正确的位置
                }
            }
    
        }
    
    

    在这里插入图片描述
    上一种写法的temp相当于A[0]
    虽然第二种后移元素的判断条件少了,算法效率有所提升,但是提升效果并不明显,所以两种写法二选一,选自己喜欢的

    在这里插入图片描述

    折半插入排序

    在查找正确的插入位置时,有没有更高效的方法,答案是有的,就是利用折半查找。
    how?
    首先我们需要3个指针:low,mid,high
    在这里插入图片描述
    待排序元素(就是i指向的元素)与mid指向的元素进行比较
    如果A[i]<=A[mid],则high=mid-1(说明元素要插入的位置在左半边)
    如果A[i]>A[mid],则low=mid+1(说明元素要插入的位置在右半边)
    查找停止条件是什么呢?
    第一次比较之后low=mid+1,mid=(low+high)/2
    在这里插入图片描述
    再下一次55<70,所以high=mid-1,mid=(low+high)/2,变成下图
    在这里插入图片描述
    最后55<60,high=mid-1,
    在这里插入图片描述
    所以查找结束的条件是:low>high
    okk,可以上代码了

     //    带哨兵的折半插入排序
        void insertSort2(int A[], int n) {
            int i, j, low, high, mid;
            for (i = 2; i <= n; i++) {
                if (A[i] < A[i - 1]) {
                    A[0] = A[i];
                    low = 1;
                    high = i - 1;
                    while (low <= high) {//折半查找插入位置
                        mid = (low + high) / 2;
                        if (A[mid] > A[0])
                            high = mid - 1;
                        else
                            low = mid + 1;
                    }
                    for (j = i - 1; j >= low; j--) {//元素后移
                        A[j + 1] = A[j];
                    }
                    A[low] = A[0];//将待排序元素插入到正确的位置
                }
            }
    
        }
    

    在这里插入图片描述

    性能分析

    分析时间、空间复杂度
    直接插入排序:只需要一个temp或者A[0]一个辅助空间,所以空间的复杂度是O(1)
    最好时间复杂度:有序的情况,对于n-1个元素每次都只需要进行一次比较,一次插入,所以最好时间复杂度为O(n)
    最坏时间复杂度:逆序的情况,对n-1个元素,第i趟排序都需要比较i+1次,移动元素i+2次,所以每趟排序的次数加和,最坏时间复杂度为O(n^2)
    在这里插入图片描述

    平均时间复杂度:O(n^2)
    折半插入排序
    对比直接插入排序的比较次数减少了,但是移动次数没有发生改变,所以整体看来和直接插入排序的时间、空间复杂度情况相同

    稳定性
    稳定,相同元素不会改变相对位置

    适用性
    对于链表,直接插入排序是适用的,而折半插入排序不适用,因为折半插入排序用到了数组(顺序表)的随机存储的特性,mid=(low+high)/2,每次都可以通过数组下标直接访问元素,但对于链表,查找元素每次都需要从头到尾查。

    链表进行直接插入排序,虽然无需每次后移大量元素,直接修改指针的指向即可,但是比较次数不变,所以整体看来与顺序表的直接插入排序的时间、空间复杂度情况相同

    希尔排序

    思维导图

    在这里插入图片描述

    拆解排序过程

    希尔是个人名,他发明了算法,所以以此命名
    希尔排序其实是对直接插入排序的一种优化,其思想是在将表划分成若个子表,将大问题切成若干小问题,先解决小问题,再逐步解决大问题,也就是先让表中元素部分有序,再逐渐逼近全表有序

    如何划分子表?

    在这里插入图片描述
    给定增量d(其实可以理解成间隔长度),将下标间隔长度为d的整数倍的元素扒拉下来,构成一个子表
    在这里插入图片描述
    然后对每个子表进行直接插入排序
    继续对d/2,直到d=1,即为普通的直接插入排序的情况,则排序完成

    希尔排序代码

    上代码

     void shellSort(int A[], int n) {
            int d, i, j;
            for (d = n / 2; d >= 1; d /= 2) {
                for (i = d + 1; i <= n; i++) {
                    if (A[i] < A[i - d]) {
                        A[0] = A[i];
                        for (j = i - d; j > 0 && A[0] < A[j]; j -= d)//当j是负数时,说明前面元素都已经比对完成
                            A[j + d] = A[j];
                        A[j + d] = A[0];
                    }
                }
            }
        }
    

    在这里插入图片描述
    切换到下一个子表进行排序是什么意思?
    刚开始对子表[49,27,76,65]进行排序
    i++后,就切换到子表[13,49,38,97]进行排序
    每次i++就切换不同子表进行排序
    在这里插入图片描述
    那难道就不可以把一个子表全部元素排序完,再进行下一个子表排序吗?
    当然可以,这样的逻辑可能更清晰,只需要要改动部分代码即可

    //一个子表排序完成,再进行下一个子表的排序
    void shellSort(int A[], int n) {
            int d, i, j;
            for (d = n / 2; d >= 1; d /= 2) {
                for (i = d + 1; i <= n; i += d) {
                    if (A[i] < A[i - d]) {
                        A[0] = A[i];
                        for (j = i - d; j > 0 && A[0] < A[j]; j -= d)//当j是负数时,说明前面元素都已经比对完成
                            A[j + d] = A[j];
                        A[j + d] = A[0];
                    }
                }
            }
        }
    

    在这里插入图片描述

    性能分析

    下面分析一下希尔排序的空间、时间复杂度
    空间复杂度:和直接插入排序一样,只用到了常量级的辅助空间,即O(1)
    时间复杂度:由于希尔排序的趟数与增量d的取值有关,其实d我们可以任取
    在这里插入图片描述
    由于d的不确定性,导致排序趟数的不确定性,所以无法准确地知道希尔排序的时间复杂度,但可以确定的是它最坏的时间复杂度是O(n2),当n在某个范围时为O(n1.3

    稳定性
    由于进行对各个子表排序时,可能会导致相同元素的相对位置变换,所以不稳定

    适用性
    由于希尔排序也是用到的随机存储的特性,每次+d来访问各子表的元素,所以仅仅适用于顺序表,不适用于链表

    交换排序

    冒泡排序

    按照升序排序(元素从小到大排序),冒泡排序就是每趟排序都确定一个元素的位置,比如第一趟将最小的元素排在下标为0的位置,第二趟将第二小的元素排在下标为1的位置。
    这过程就像每个泡泡按照大小依次升到自己正确的位置
    在这里插入图片描述
    大致步骤分为:
    1.确定排序的趟数 n-1
    2.确定每次交换的元素
    3.确定排好序的条件

    从后往前,对比前后两个元素,如果后元素小于前元素,则交换两元素,否则不变,直到到达上一趟已排好元素的末尾
    在这里插入图片描述
    已排好元素13的位置
    在这里插入图片描述
    那么什么时候排序结束呢?
    当然n-1个元素全部都排好序就结束了(n-1个已有序,即n个也有序了)
    有没有提前结束排序的条件呢?
    有的,当某一趟的排序中没有出现元素的交换,就说明顺序表已经全部有序了,提前结束排序

    上代码

    void swap(int &a,int &b){
            int temp=a;
            a=b;
            b=temp;
       }
    void bubbleSort(int A[],int n){
            for(int i=0;i<n-1;i++){
                bool flag=false;//本趟排序是否发生交换的标志
                for(int j=n-1;j>i;j--){
                    if(A[j]<A[j-1]) {
                        swap(A[j], A[j - 1]);
                        flag = true;
                    }
                }
                if(flag==false)//本趟没有交换元素,说明数组已经基本有序
                    return;
            }
       }
    

    从后到前,每次将最小的往前冒泡
    当然也可以从前往后冒泡,每次将最大的往后冒泡

    //从前到后冒泡
    void bubbleSort(int A[],int n){
            for(int i=0;i<n-1;i++){
                bool flag=false;//本趟排序是否发生交换的标志
                for(int j=0;j<n-i-1;j++){//从前到后冒泡
                    if(A[j]>A[j+1]) {
                        swap(A[j], A[j + 1]);
                        flag = true;
                    }
                }
                if(flag==false)//本趟没有交换元素,说明数组已经基本有序
                    return;
            }
       }
    

    性能分析
    空间复杂度:只需要几个temp,i,j常数级的辅助变量,O(1)
    时间复杂度:
    最好:有序,第一趟排序遍历整个数组没有发生任何交换,O(n)
    最坏:倒序,将每趟交换元素次数加和(n-1)+(n-2)+…+1,O(n2
    平均:O(n2
    稳定性:稳定,每次交换都必须时严格>或<

    适用性
    适用于顺序表和链表

    注意
    交换次数不等于移动元素次数,因为每次交换元素都需要用到swap函数,每次调用swap函数都需要移动元素3次,故1交换=3次移动

    快速排序

    重要!!!快速排序我愿称之为yyds,这个名字就给人一种这算法很🐂🍺的感觉,他是所有内部排序算法中平均性能最优的算法
    对比冒泡排序,每趟排序都是将最大或最小的元素排好序,
    快速排序,则是每次将中间的元素排好序

    我们一般选取一个基准(或者说是枢轴),将比它小的元素放在它左边,比它大或相等的元素放在它的右边,这样的过程我们称之为一次划分

    图中的黄柱子就是一个基准
    在这里插入图片描述
    我们一般选取第一个元素作为基准,按照划分的规则,将比它小的元素放在它左边,比它大或相等的元素放在它的右边
    how?
    设置两个指针low和high,初始指向位置如图,如果从high开始,一直high–直到找到比49小的元素则将它赋值到low的位置,即A[low]=A[high]
    找到之后,切换到low指针,low++一直到找到大于49或者=49的位置,则将它赋值到high的位置,即A[high]=A[low]
    直到low和high指针重合,则找到了49的位置
    在这里插入图片描述
    在这里插入图片描述
    这样我们就成功将一个数组分成了两部分,然后对左半部分和右半部分都执行同样的操作,直到一个子表内只存在一个元素或为空,即可完成全部的排序

    这就是分治算法的思想,分而治之

    上代码

        int partition(int A[], int low, int high) {
            int pivot = A[low];//pivot是基准的意思
            while (low < high) {
                while (low < high && A[high] >= pivot) high--;
                A[low] = A[high];
                while (low < high && A[low] <= pivot) low++;
                A[high] = A[low];
            }
            A[low] = pivot;//这里high和low指针重合,写high也可以
            return low;
        }
    
        void quickSort(int A[], int low, int high) {
            if (low < high) {
                int pivotPos = partition(A, low, high);//将表分别为左右两子表
                quickSort(A, low, pivotPos - 1);//左子表递归
                quickSort(A, pivotPos + 1, high);//对右子表递归
            }
        }
    

    分治就像是切一块大蛋糕,直到切到你能够吃得下的一小块
    就先快速排序的划分,先中间来一刀,左半边大了,左半边来一刀,右半边大了再来一刀;直到子表只剩下一个元素或没有元素,就结束啦~
    在这里插入图片描述
    更加详细的递归过程,戳视频https://www.bilibili.com/video/BV1b7411N798?p=81

    性能分析
    无论是空间还是时间复杂度还是空间复杂度,都与递归的深度有关
    空间复杂度:O(递归深度)
    时间复杂度:O(n*递归深度)
    不理解的话,讲的超清晰的,戳视频https://www.bilibili.com/video/BV1b7411N798?p=81
    在这里插入图片描述
    在大O表示法的log的底数不重要,所有一般省略底数不写
    空间复杂度
    最好:O(logn)
    最坏:O(n)
    时间复杂度
    最好:O(nlogn)
    最坏:O(n2
    平均:O(nlogn)
    稳定性:不稳定,对于像是希尔排序,快速排序,出现了划分子表的部分,一般算法都是不稳定的,就像下图两个子表顺序交换后,两个元素的相对位置也就发生了变化
    在这里插入图片描述
    适用性
    适用于顺序表和链表(双向链表),由于需要high指针从后往前的操作,所以需要单链表不太行(但是也勉强可以,每次从头开始遍历,效率上要差很多)

    选择排序

    简单选择排序

    顾名思义真的简单,每次在待排序的表中选取最小的元素的与前面的元素进行交换,共进行n-1次交换即可
    在这里插入图片描述

    在这里插入图片描述
    上代码

     void swap(int &a, int &b) {
            int temp = a;
            a = b;
            b = temp;
        }
    
        void selectSort(int A[], int n) {
            for (int i = 0; i < n - 1; i++) {
                int min = i;
                for (int j = i + 1; j < n; j++) {
                    if (A[j] < A[min])
                        min = j;
                    if (min != i)
                        swap(A[i], A[min]);
                }
            }
        }
    

    性能分析
    空间复杂度:O(1)
    时间复杂度:由于每趟排序都要从前到后扫描到最小的元素,所以比较次数为(n-1)+(n-2)+…+1=n(n-1)/2次排序,即O(n2
    稳定性
    不稳定
    在这里插入图片描述

    适用性
    适用于顺序表和链表

    堆排序

    堆排序是个重头戏,认真学习脸
    堆排序也是选择排序的一种,它每次选择表中最大或最小的元素加入有序队列中

    首先要知道什么是堆?
    堆分为大、小根堆
    大根堆就是所有子树的根的值都大于它的孩子的值
    小根堆则是所有子树的根的值都小于它的孩子的值
    如图观察箭头指向的结点是都大于它的孩子结点,所以这样二叉树就是一个大根堆,类比也可知小根堆是什么样的了
    在这里插入图片描述
    知道什么是堆之后,就要知道它和我们待排序的数组有什么联系吗?
    在这里插入图片描述
    可以观察到其实就是将数组中的元素按层次遍历的顺序存入,就对应了一颗二叉树
    在这里插入图片描述

    那如何将一个初始数组调整成大根堆的形式呢?
    答案是:从后往前遍历每个非终结结点(非叶子结点),比较它与它左右孩子的值,将大的值往上提,小的值往下坠

    具体操作就是
    按照09 78 17 53从后往前顺序依次调整大根堆
    观察到32>9,所以交换32和9的位置,
    然后87>78,所以交换78和87的位置
    ……
    以此类推
    在这里插入图片描述
    来到最后一个结点也就是A[1]结点进行调整
    87>53,所以交换87和53

    在这里插入图片描述
    交换完就会发现78>53,还需要继续调整,也就是53与78交换,此时53这个元素已经到叶子结点的位置了(也就是盛底了),那就调整结束了
    在这里插入图片描述
    在这里插入图片描述
    至此我们得到了我们的初始的大根堆,那如何用它来排序呢?
    1.那就要利用大根堆的性质:根元素一定是整个数组中最大的,将它与最后一个元素交换,于是便排好1个元素的位置,
    2.剔除该元素,调整成新的大根堆,此时又出现了新的元素根元素重复上述步骤
    3.直至堆中只剩下一个元素,即排好序了
    在这里插入图片描述
    对于一些树的参数说明:
    对于一个以i为结点的根
    它的左孩子下标:2i
    它的右孩子下标:2i+1

    代码实现

        //交换元素
        void swap(int &a, int &b) {
            int temp = a;
            a = b;
            b = temp;
        }
    
        //建立大根堆
        void buildMaxHeap(int A[], int len) {
            for (int i = len / 2; i > 0; i++) {//对所有非叶子结点调整成大根堆
                heapAdjust(A, i, len);
            }
        }
    
        //调整以k为根的非叶子结点为大根堆
        void heapAdjust(int A[], int k, int len) {
            A[0] = A[k];
            for (int i = 2 * k; i <= len; i *= 2) {//遍历每个结点的左孩子
                if (i < len && A[i] < A[i + 1])//对比左右两个孩子的大小,
                //i<len该结点是有右孩子的,即A[i+1]存在
                    i++;
                if (A[0] >= A[i]) break;//对比子树根节点与孩子结点的大小
                else {
                    A[k] = A[i];//将孩子结点的较大值赋给A[k]
                    k = i;//修改k,继续向下调整
                }
            }
            A[k] = A[0];
        }
    
        void heapSort(int A[], int len) {
            buildMaxHeap(A, len);
            for (int i = len; i > 1; i--) {
                swap(A[i], A[1]);
                heapAdjust(A, 1, i - 1);//剔除一个已排好序的元素,即长度i-1,
                //由于交换了A[1]和最后一个元素,所以每次都需要对以1为根的子树进行调整
            }
        }
    

    性能分析

    空间复杂度O(1)

    时间复杂度
    建堆O(n),排序O(nlogn)
    总的:O(n)+ O(nlogn) = O(nlogn)

    稳定性
    不稳定

    适用性
    适用于数组和链表(不适用于单链表,由于每次排序都要交换第一个元素和最后一个元素,需要双链表的支持)

    利用大根堆——得到递增序列
    利用小根堆——得到递减序列

    归并排序

    本质是将多个有序表合并成一个有序表
    k路归并排序,意思是合并时子表的数目是k个(一般用于外部排序)
    比如2路归并排序,就是将两个有序子表合成一个有序表(一般用于内部排序)

    如何合并呢?
    就是如图三个指针,每次比较i,j指向的元素的大小,每次将较小的元素赋值给k所指的位置

    在这里插入图片描述
    观察到7<12,所以将j指向的元素赋值到k所指向的位置,然后k++,j++
    10也<12,所以将j指向的元素赋值到k所指向的位置,然后k++,j++
    在这里插入图片描述
    直到i,j的其中一个指针走到了尽头
    此时直接将还未走到尽头的i指针所指向的元素一一赋值到k处即可,无需再与j的元素对比
    在这里插入图片描述
    具体代码实现的话就需要一个辅助数组B[n],用来暂存数组元素进行比较元素的操作,使得A数组可以存放合并后的有序表
    在这里插入图片描述

    int n=10;
    int B[n];//报错array bound is not an integer constant
                //定义数组时必须用整型常量指定数组长度即B[100]的形
    int *B=(int *)malloc(n*sizeof(int));//方式2动态分配数组长度,用一个指针+malloc分配内存空间函数
         void merge(int A[], int low, int mid, int high) {
            int i, j, k;
            for (k = low; k <= high; k++) {//将A表元素一一复制到B表
                B[k] = A[k];
            }
            for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
                if (B[i] <= B[j])//i指向左子表,j指向右子表,k指向最终合并的总表
                    A[k] = B[i++];//由于这里是<=所以该算法是稳定的,因为对于=的情况,元素相等位置不会变
                else
                    A[k] = B[j++];
            }
            while (i <= mid) A[k++] = B[i++];//这句相当于三句A[k]=B[i] i++ k++
            while (j <= high) A[k++] = B[j++];
        }
    
        void mergeSort(int A[], int low, int high) {
            if (low < high) {
                int mid = (low + high) / 2;//划分成两个子表
                mergeSort(A, low, mid);//左半排序
                mergeSort(A, mid + 1, high);//右半排序
                merge(A, low, mid, high);//将两个有序的子表合并
            }
        }
    

    注意这里有个语法点可能会有点迷惑

     //这句相当于三句A[k]=B[i] i++ k++
     while (i <= mid) A[k++] = B[i++];
    
    

    其实就是先++还是先赋值的问题=
    假设a=0,b=0
    如果是a=b++,就相当于先a=b,后b++ //即a=0,b=1
    如果是a=++b,就相当于先b++,后a=b //即a=1,b=1

    性能分析
    空间复杂度:O(n),因为主要用到了B一个辅助数组
    时间复杂度:归并的趟数O(logn),每趟需要O(n)次对比,总的即O(nlogn)
    稳定性:稳定
    适用性:仅适用于顺序表,不适用于链表,由于划分子表需要(low+high)/2,用到了随机存储的特性

    基数排序

    基数排序 是一种特殊的排序,它和以上排序不同的点在于它的排序不基于比较,而是基于数本身的大小,什么意思?
    给定这么一个表
    在这里插入图片描述
    按照它个位数字的不同分配到不同的Q下面,这叫一次分配
    在这里插入图片描述
    然后喊着从左到右的顺序,从上到下的顺序将元素串联起来,这叫一次收集
    在这里插入图片描述
    而后将本次收集的队列重复上述步骤,只不过这次按照十位数的大小进行分配和收集,又得到一个新的队列
    在这里插入图片描述
    在这里插入图片描述
    最后按照百位进行分配收集
    在这里插入图片描述
    在这里插入图片描述
    此时得到的队列就是一个递减队列,由于是按照个十百的顺序进行排序,每一趟的排序都是基于前一趟的排序结果,所以保证了最后得到的数列是一个递减数列

    这里考察代码实现的可能性不多,但是我们要知道大概的原理
    基数排序一般是基于链表实现的
    在这里插入图片描述
    如图,我们需要定义两个结构体

       typedef struct LinkNode{
            int data;
            struct LinkNode *next;
        }LinkNode, *LinkList;//其实前一个强调是结点,后一个强调是整个链表
    
        typedef struct LinkQueue{//链式队列
            LinkNode *front,*rear;//首尾
        }LinkQueue;
    
    

    如果对链式队列的定义的写法有疑惑的可以戳这里

    性能分析
    进行性能分析之前,先约定,
    d:代表分组数量,如上面的例子分成个十百位,即d=3
    r:代表一个分组内的不同取值的数量,如上面例子中的一个十进制数,共10种不同的状态,即r=10
    空间复杂度:O(r),由于需要一个辅助的队列,队列的大小基于r
    时间复杂度:O(d(n+r)),总共需要d趟的分配和收集,分配是将元素全部扫描一遍放到合适的分组即O(n),收集是扫描一个分组内所有取值,将元素依次串联即O(r)
    如图,收集时我们要将666和996拼接到007后面,我们无需扫描666和996这一整个队列,而是直接修改几个指针就可以了,时间复杂度O(1),要将Q9-Q0所有队列都连接起来,即O(r)
    在这里插入图片描述

    稳定性:稳定
    适用性:适用于顺序表和链表

    应用
    下面这样一个例子中的每个分组的取值个数是不同的,即r是不同的,说明了基数排序完全可以灵活调整r的取值以适应不同的应用,而非一成不变的
    在这里插入图片描述
    假设n=10000,计算各类算法的时间复杂度,对比可知基数排序在这里在这个例子的应用是十分优越的
    在这里插入图片描述
    那基数排序适用的场景有什么共通的特点吗?
    在这里插入图片描述

    外部排序

    前面也说过外部排序就是指,数据有部分在外存上的(这里特指磁盘,也叫机械硬盘)
    在这里插入图片描述
    外存和内存交换数据都是以块为单位的,什么是块,就是
    在这里插入图片描述
    你我之间互换板砖,只能一块一块交换,不能掰成两半,一半一半给我,也不能揉碎了成渣了给我

    那如何对磁盘内的数据进行排序呢?
    在磁盘内是不能排序的,于是我们需要将数据传到内存,
    假设现在内存区域有三个缓冲区,如图,此时可以将磁盘的两块读入内存,在内存中的数据就可以用上述提到的所有内部排序算法进行排序了
    在这里插入图片描述
    排完序之后就变成下图的模样
    在这里插入图片描述
    之后写回磁盘即可,依次类推对16块进行上述操作,便得到了8个我们称之为初始归并段的东西,也就是8个排好序的段
    在这里插入图片描述
    之后我们要进行归并操作,各选取两个归并段较小的一段到内存,然后用归并排序得到一个[1,8,9]一块,写回磁盘
    在这里插入图片描述
    如果输入缓冲区有一个空了,就需要立刻在磁盘对应的归并段再读入一个块
    在这里插入图片描述
    最终我们将两个较短的归并段,归并成了一个更长的有序序列
    在这里插入图片描述
    以此类推,我们可以每趟归并,都可以合成一个更长的有序序列,直到磁盘全部元素有序

    在这里插入图片描述
    在这里插入图片描述
    至此我们总结一下外部排序的过程
    在这里插入图片描述
    算法优化
    在这里插入图片描述
    之前也提到过,外存的读写的速度远大于内存读写速度,也远大于内部排序所需要的时间,所以研究外部排序时间主要就是研究读写外存时间,而读写外存的时间取决于外存读写次数,我们希望读写次数越少越好

    how?
    两种方式,
    一种增加内存输入缓冲区的数量
    另一种则是减少归并段的数量
    就好比下图
    在这里插入图片描述
    当我们增大了输入缓冲区的数量时,其实也在变相增大了初始归并段的长度,因为一次可以读入4个块,同时对4个块进行内部排序,再写回磁盘
    此时我们初始归并段的数量就减少了,从而优化了我们的算法
    在这里插入图片描述
    但是不是输入缓冲区的数量越多越好呢?
    nonono
    1.输入缓冲区数量增多会增加内存开销
    2…输入缓冲区数量增多会造成每次归并的元素的比较次数增多,2路归并每次需要比较1次比较,而n路归并每次需要n-1次比较
    对归并次数有疑惑的可以向上查看👆归并排序的相关知识

    外部排序的优化——败者树

    其实可以把它看作是一颗比拼树,每次的胜利者可以进入下一回合,直到决出冠军,这样一共8名选手,7场比拼就结束了比赛
    在这里插入图片描述
    假设现在比拼结束,决出冠军是我们的天津饭选手,此时天津饭选手很高兴拿着奖金跑路了,新来了一名选手派大星,它也想来和各位高手一决高下
    在这里插入图片描述
    我们是否需要每名选手都像第一次一样再打一轮呢?
    不不不,我们只需在人员变动处进行比拼即可,因为看右半边选手还是原来的样子,实力已经在第一次比拼中决出高低,没必要比拼。
    那就是需要
    派大星——阿乐(派大星胜利)
    派大星——程龙(派大星胜利)
    派大星——孙悟空(孙悟空胜利)
    本次比赛最多需要3场比拼就结束了
    这次比拼数大大减少了!
    在这里插入图片描述
    外部排序我们说过可以通过增大内存缓冲区的大小,即增加归并的路数,从而减少磁盘读写次数,但也引来的新问题——归并时的比较次数增加了
    k路归并——k-1次比较
    在这里插入图片描述
    此时败者树就可以运用在这,以减少比较次数
    在这里插入图片描述
    败者树其实就是一颗完全二叉树+一个多出的结点
    那一趟归并过程总共需要比较几次元素呢?(k代表结点个数,也就是归并段个数)
    在这里插入图片描述
    log2k相当于除去最上面结点的败者树的层数
    那具体如何编程实现败者树呢
    很简单,只需要定义一个int型数组
    在这里插入图片描述

    外部排序优化——置换选择排序

    我们提到过外部排序的优化有两个思路:
    1.增加归并路数
    2.减少初始归并段的个数
    第一种思路我们用了败者树做优化
    第二种思路就可以用到我们的置换选择排序

    之前我们构造初始归并段的时候是——能装多少就先排多少
    在这里插入图片描述
    于是乎初始归并段的个数=16/2=8个

    置换选择排序就是——我不管能装几个,就要尽量多拍好序几个

    具体过程就是:
    1.将3个记录写入内存工作区WA(work area)

    在这里插入图片描述
    2.将每次将WA中最小的放到归并段中
    3.刚放入归并段的记录的值放到变量miniMax中
    在这里插入图片描述
    4.再读入一个记录到WA的空闲处
    在这里插入图片描述
    5.循环上述过程直到一个归并段出现WA中最小的记录也大于miniMax,即最小的元素也无法保证一个递增的归并段(说的复杂,看图很好理解)
    那我们就放第2小的记录到归并段
    在这里插入图片描述
    6.当所有元素都是都小于miniMax时,就可以开始构造第二个归并段了
    在这里插入图片描述
    最后构造好的初始归并段如图
    在这里插入图片描述
    置换选择排序——每次选择小的元素构建归并段,并将磁盘中的数据写入内存置换小的元素

    我们发现置换选择排序构造的初始归并段只有3个!对比老方法构造的8个,少了不少,nice

    但也有个疑问怎么整个过程中都一个一个记录进行的,不是说好了磁盘和内存中间的数据交换都是以块作为单位吗?
    没错,这里只是简化的过程,其实输出输入都有个缓冲区,每次输入3个记录(假设一块=3个记录)然后一个记录一个记录放入WA中,输出也一样,一次将一个记录放到输出缓冲区,凑齐了3个即一块,即一起输出到磁盘。
    在这里插入图片描述

    最佳归并树(哈夫曼树)

    老方法构造初始的归并段,每个归并段的磁盘块数量一般是一样的(除了最后一个段可能不同)
    在这里插入图片描述
    而置换选择排序构造的初始归并段,各段的磁盘块数一般是不同的
    在这里插入图片描述
    R1-R5表示各个归并段,圆圈里的数字表示一个归并段中的磁盘块数
    在这里插入图片描述
    而磁盘速写次数与每次归并时,归并段的中的块数有关,比如选择R1,R2归并,需要读写各2+5=7次,总共7*2=14次,
    那此时归并段进行归并的先后次序就很重要了,我们将每次归并的读写次数作为一个结点的权值
    按照如图所示进行二路归并,这不就是构造一个带权二叉树吗
    在这里插入图片描述
    为了使得磁盘总读写次数最少,不就是求这颗树的带权路径长度最小的树吗——即哈夫曼树
    关于哈夫曼树:哈夫曼树

    哈夫曼树的构造
    每次都选取元素最小的两个结点进行合并
    在这里插入图片描述
    上述是2路归并的做法,如果是多路归并呢(即>2)
    以3路归并为例:照葫芦画瓢,那就是每次选取最小的3个结点进行归并
    没错
    在这里插入图片描述
    但又不全对,这又不全对,假设初始没有30这个结点,那按照这个方法得到的树并不是最优的,因为在最后一次的归并,即32和59的归并非3路归并
    在这里插入图片描述
    此时我们需要增加一个0结点,以保证每次归并都是3路归并,此时得到的归并树就是最佳的
    在这里插入图片描述
    那我怎么知道要补上几个这样的0结点呢?
    在这里插入图片描述
    举个例子,对于8个结点,需要进行3路归并以构造最佳归并树,
    k=3(3叉树)
    n初始=8
    (8-1)%(3-1)=1
    (3-1)-1=1
    所以需要补充1个虚段

    在这里插入图片描述

    展开全文
  • 基本的五类排序算法(插入,选择,交换,归并,基数排序)。排序:将数据元素的一个任意序列,重新排列成一个按关键字有序的序列。 排序的稳定性:待排序列中有大于等于2个相同的项,且排序前后,相同项的相对位置...
  • 一、直接插入的基本思想 ...如此往复,经过n-1次插入后,未排序序列中的元素个数变为0,排序完成。如下图所示 代码及上下界如图 从代码可以看出,空间复杂度上,简单插入排序仅需要常数个额外空间 在...
  • 并归排序图解

    2018-07-07 15:32:23
    所以,归并排序其实要做两件事:(1) 分解:将序列每次折半拆分。(2) 合并:将拆分开的两个序列排序后合并。只要理解了归并排序的思想,就很容易实现归并排序。...
  • 折半插入排序利用二分法的思想,在一个有序的序列中,找到新元素在该序列中的位置,然后插入。如图1所示,共有n个元素,前i个元素已经是有序序列,现在要将第i个元素插入其中。折半插入排序需要做两步工作:找到待...
  • 本文的代码来自于《数据结构与算法(JAVA语言版)》,是笔者在网上找到的资料,非正式... 折半插入排序方法的思想是,先以第一个数为基准,作为一个有序的数列,依次把它后面的数字以折半的方式插入这个有序的数列。...
  • 排序算法3——图解直接插入排序以及折半(二分)插入排序及其实现 排序算法4——图解希尔排序及其实现 排序算法5——图解排序及其实现 排序算法6——图解归并排序及其递归与非递归实现 基本思想 通过一趟...
  • 折半/二分查找算法 冒泡排序算法 插入排序算法 选择排序算法 这里是从小到大排列 原理: 从待排序序列中取一个元素为基准(任意选取,可以取开头、结尾或者中间元素), 把剩下元素依次与基准元素比较,大于基准...
  • 折半/二分查找算法 插入排序算法 选择排序: 是最简单直观的排序算法, 选择排序是不稳定的排序方法,具体见:选择排序 工作原理: 第一次从所有元素中选出最小元素,放到list最开始位置, 第二次从剩下元素中选出...
  • 插入排序实现--图解/实例/java/php

    千次阅读 2018-11-06 18:00:07
    插入排序 ...需要注意的是,在往有序数组插入一个新元素的过程中,我们可以采用按顺序循环比较,也可以通过折半查找法来找到新元素的位置,两种方式的效率取决于数组的数据量 最坏时间复杂度O...
  • 折半/二分查找算法 冒泡排序算法 插入排序算法 选择排序算法 快速排序算法 希尔排序算法 希尔排序算法是在插入排序的基础上进行的改进,比插入排序更高效,是插入排序的一种,又叫‘缩小增量排序’。 希尔排序是把...
  • 上篇文章我们学习了折半插入排序,该排序算法的原理是在顺序插入查找插入过程中使用折半查找法从而提高插入效率,为此,我们可以思考一下是否还有办法能够使插入的效率更高呢? 基于此,希尔排序诞生了,希尔排序的...
  • 折半/二分查找算法 插入排序: 一般称为直接插入排序,对于少量的元素排序,比较高效, 这里使用的顺序是正序,从小到大排列, 基本思想: 每一步将一个待排序的数据插入到前面已经排好序的有序序列中,直到插完...
  • 折半/二分查找算法 冒泡排序算法 插入排序算法 选择排序算法 快速排序算法 希尔排序算法 1、堆定义: 堆被看作是一个完全二叉树的数组对象, 满足条件: 是一个完全二叉树, 每个小堆的父节点总是大于等于或者小于...
  • 插入排序和希尔排序

    2020-08-14 21:40:22
    希尔排序图解 直接插入排序 折半插入排序 直接插入排序 直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已经排序号的有序表中,从而得到一个新的,记录数量增1的有序表...
  • 文章目录各种排序算法及其复杂度分析插入排序直接插入排序基本思想图解代码实现算法分析折半插入排序基本思想代码实现算法分析希尔排序图解代码实现算法分析快速排序基本思想伪码描述图解代码实现算法分析堆排序建立...
  • 目录 1.选择排序 1.1 基本思想 1.2 图解原理: 1.3 Java代码实现 1.4 性能分析 ...2.插入排序 ...2.2 图解原理 ...(2)直接插入排序折半插入排序性能测试代码:(输入数据为随机数据) 3.三种基于比较的...
  • 排序算法】— 手写堆排序

    千次阅读 2020-10-12 11:04:15
    插入类排序—(折半)插入排序、希尔排序 交换类排序—冒泡排序、快速排序手撕图解 归并类排序—归并排序(逆序数问题) 计数排序引发的围观风波——一种O(n)的排序 两分钟搞懂桶排序 对于常见的快排、归并这些O(nlogn)...

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

折半排序图解