10种排序算法（Python例子）

谁借莪１个温暖的怀抱￠ 2022-02-28 14:30 197阅读 0赞

### 文章目录 ###

*  10种排序算法
 *   *  时间复杂度知识点
 *  1.选择类排序
 *   *  1.1 冒泡排序：
     *  1.2 快速排序
 *  2.插入类排序
 *   *  2.1 直接插入排序
     *  2.2 shell排序（缩小增量排序）
 *  3.选择排序
 *   *  3.1 简单选择排序（又称直接选择排序）
     *  3.2 堆排序
     *   *  堆排序图解：
 *  4.归并类排序
 *   *  4.1 归并排序
 *  5.线性时间非比较类排序
 *   *  5.1 计数排序
     *  5.2 基数排序
     *  5.3 桶排序

# 10种排序算法 #

给定一个无序数列，将数列中的数有效的排序。（降序升序不限）

## 时间复杂度知识点 ##

空间复杂度：空间消耗越多称为空间复杂度（也就是内存消耗情况）  
时间复杂度：时间消耗多少称为时间复杂度  
复杂度表示有：

*   O ( 1 ) O(1) O(1) ：常数，不会随数据的增加而改变。  
    例如：完成只需要1次，或者完成只需要10次，都不会随数据的增加而改变。
 *   O ( n ) O(n) O(n): 变量，会随数据的改变而改变
 *   O ( n log ⁡ 2 n ) O(n\\log\_2n) O(nlog2n): 会随数据的改变而改变，当n越大时，变量越小。
 *   O ( n 2 ) O(n^2) O(n2): 变量，会随数据的改变而改变。平方级增加

# 1.选择类排序 #

## 1.1 冒泡排序： ##

*  冒泡排序是一种简单的排序算法，其原理是依次遍历整个数组，一次比较两个元素，如果他们顺序错误，就把他们交换过来。走访数列的工作是重复地进行，指导没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或者越大）的元素会经交换慢慢的“浮”到数列的顶端。  
    *算法步骤：*

1.  从数组中第一个数开始，一次与下一个数比较并交换比自己小的数，直到最后一个数。如果发生交换，则继续下面的步骤，如果未发生交换，则数组有序，排序结束，此时时间复杂度为：O(n)
2.  每一轮“冒泡”结束后，最大的数将出现在乱序数列的最后一位。重复步骤（1）

*  **时间复杂度**：O(n)至O( n 2 n^2 n2)，平均时间复杂度为：O( n 2 n^2 n2)
 *  **最好情况**：如果待排序序列数据为正序，则一趟冒泡就可以完成排序，排序的比较次数为n-1次，且没有移动，时间复杂度为：O(n)
 *  **最坏情况**：如果带待排序列为逆序，则冒泡排序需要n-1趟，每趟进行n-i次排序的比较和移动，即比较和移动的数均达到最大值。比较次数为： C m a x = ∑ i = 1 n − 1 ( n − i ) = n ∗ ( n − 1 ) 2 = O ( n 2 ) C\_\{max\}=\\sum^\{n-1\}\_\{i=1\}(n-i)=\\frac\{n\*(n-1)\}\{2\}=O(n^2) Cmax=∑i=1n−1(n−i)=2n∗(n−1)=O(n2)  
    python代码如下

arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    for i in range(1,len(arr)):
        booll = True
        for k in range(len(arr)-i):
            if arr[k] < arr[k+1]:
                arr[k] = arr[k+1]^arr[k]
                arr[k+1] = arr[k+1]^arr[k]
                arr[k] = arr[k+1]^arr[k]
                booll = False
        if booll:
            break    
    print(arr)

*  冒泡排序相应的java代码如下：

/** * 冒泡排序 * @param arr * @return */
    public static int[] bubbleSort(int[] arr){ 
    	Boolean booll;
    	for(int i=1;i<arr.length;i++){ 
    		booll = true;
    		for(int k=0;k<arr.length-i;k++){ 
    			if(arr[k]<arr[k+1]){ 
    				arr[k] = arr[k]^arr[k+1];
    				arr[k+1] = arr[k]^arr[k+1];
    				arr[k] = arr[k]^arr[k+1];
    				booll = false;
    			}
    		}
    		if(booll) break;
    	}
    	return arr;
    }

## 1.2 快速排序 ##

*  冒泡排序是在相邻的两个记录进行交换，每次交换智能上移或下移一个位置，导致总的比较与移动次数较多。快速排序又称为分区交换排序，是对冒泡排序的改进，快速排序采用的思想是分治思想。
 *  算法原理：
    
    1.  从待排序的n个记录中任意选取一个记录（通常选取第一个记录，这里的代码例子选取为最后一个记录）为分区标准：即分界值
    2.  对任意一个待排序的集合，把所有小于该排序的记录移动到左边，把所有大于该排序的记录移动到右边，中间放所选记录，称为第一趟排序；每第一趟排序结束后，都会找出分界值在数组中实际的位置。分界值左边的值<=分界值<=分界值右边的值
    3.  对前后两个序列分别重复上述过程。直到所有记录都排好序列。即，分到无法分界。也就是集合中最后一个不知道序列的值找到了自己的对应位置。
 *  **稳定性**：不稳定排序
 *  **时间复杂度**： O ( n ∗ log ⁡ 2 n ) O(n\*\\log2n) O(n∗log2n)至 O ( n 2 ) O(n^2) O(n2),平均时间浮渣度为 O ( n ∗ lg ⁡ n ) O(n\*\\lg n) O(n∗lgn)
 *  **最好的情况**：是每趟排序结束后，每次划分使两个子文件的长度大至相等，时间复杂度为 O ( n ∗ log ⁡ 2 n ) O(n\*\\log2n) O(n∗log2n)。
 *  **最坏的情况**：是待排序记录已经排好序，第一趟经过n-1次比较后第二个记录保持位置不变，并得到一个n-1的元素的子记录；第二趟经过n-2次的比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件，依次类推，这样总的白交次数是：  
     C m a x = ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) 2 = O ( n 2 ) C\_\{max\}=\\sum^\{n-1\}\_\{i=1\}(n-i)=\\frac\{n(n-1)\}\{2\}=O(n^2) Cmax=∑i=1n−1(n−i)=2n(n−1)=O(n2)

python代码如下

##快速排序
    def quickSort(arr,low,high):
        if low >= high: return  #设置递归出口，如果分界值的左边界大于或等于分界值的右边界。则证明分界值可以结束递归。该组合已经排好序列
        left = low   #记录左边界
        right = high  #记录右边间
        key = arr[right]  #默认筛选最右边的值为分界值
        ## 循环完成后，会找出分界值实际在数组中应该存放的位置，和小于分界值的一部分，以及大于分界值的一部分。
        while left < right :
            while left < right and arr[left] <= key : left += 1   #从左边开始查找，找出一个大于分界值放在右边
            arr[right] = arr[left]
            while left < right and arr[right] >= key : right -=1  #从右边开始查找，找出一个小于分界值的值放在左边
            arr[left] = arr[right]
        arr[right] = key     #循环完成后找到分界值的位置。放入分界值。
        quickSort(arr,right+1,high)  #将分界值右边的部分再按照上述方法继续寻找
        quickSort(arr,low,right-1)  #将分界值左边的部分再按照上述方法继续寻找
    
    quickSort(arr,0,len(arr)-1);
    print(arr)

*  对应的java代码如下

/** * 快速排序 * @param arr 代派数组 * @param low 最低位的下标 * @param high 最高位的下标 */
    public static void quickSort1(int[] arr,int low,int high){ 
    	if(low>=high) return;
    	int left = low;
    	int right = high;
    	int key = arr[right];//默认用数组的最后一个值作为分区元素
    	/*while循环结束，会确定key在数组中实际存在的位置，并将数组分为小于key的部分，和大于key的部分*/
    	while(left<right){ 
    		while(left<right && arr[left]<=key) left++; //从左向右扫描，找到第一个值大于key的值，并交换
    		arr[right] = arr[left];
    		printList(arr);
    		while(left<right && arr[right]>=key) right--;//从右向左扫描，找到第一个值小于key的值，并交换
    		arr[left] = arr[right];
    		printList(arr);
    	}
    	arr[left] = key;
    	printList(arr);
    	quickSort1(arr, low, right-1);
    	quickSort1(arr, right+1, high);
    }

*  **优化**：在上面的快速排序中，如果先从左边left位置开始查找，当找到left对应的值大于key，将key的值放在空缺位right上，而在从right上继续寻找时，会出现一次重复比较。可以如下优化

import random
    arr = [random.randint(0,20) for _ in range(30)]
    arr2 = arr.copy()
    ##快速排序，从待排序列中选择一个值，比这个值小的放在左边，大的放在右边，依次再从待排序列中选择值，直到，待排序列只有一个元素。结束递归
    def quicksort(arr:list,left:int,right:int)->None:
        if left>=right:
            return
        key = arr[right] #默认取最右边的值为中间值
        minindex = left
        maxindex = right
        while minindex != maxindex:
            while minindex < maxindex and arr[minindex]<=key: minindex +=1
            if maxindex > minindex: #防止自我插入
                arr[maxindex] = arr[minindex]
                maxindex -= 1 #防止重复比较
            while minindex < maxindex and arr[maxindex]>key: maxindex -=1
            if maxindex > minindex: #防止自我插入
                arr[minindex] = arr[maxindex]
                minindex += 1  #防止重复比较
        arr[minindex] = key
        quicksort(arr,left,minindex-1)
        quicksort(arr,minindex+1,right)
        
    quicksort(arr,0,len(arr)-1)
    print(arr)
    arr2.sort()
    print(arr2)

*  快速排序第二种实现：分而治之+递归
    
     *  根据上面的快速排序分析，相当于对数据进行分组，分组结构如下：  
        **小于基础值的部分  ⇉ \\rightrightarrows ⇉ 基础值  ⇉ \\rightrightarrows ⇉ 大于基础值的部分。**  
        按照这个条件，结合python语法。可以如下简单实现快速排序

##第二种思路实现python的快速排序
    arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    def quickSort3(arr):
        if(len(arr)<2) : return arr
        key = arr.pop(len(arr)-1) #从元数据中移除基本值,并将值选取为基础值
        leftarr = []
        rightarr = []
        alike = []
        for i in arr:
            if key > i:
                leftarr.append(i)
            elif key == i:
                alike.append(i)
            else:
                rightarr.append(i)
        return quickSort3(leftarr) + [key]+ alike + quickSort3(rightarr)
    print(quickSort3(arr))

**快速排序算法优化：**

*  **三平均分区法**：  
    　　关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：
    
    1.  首先，它使得最坏情况发生的几率减小了。
    2.  其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。
 *  **根据分区大小调整算法**  
    　　这一方面的改进是针对快速排序算法的弱点进行的。快速排序对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计，因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术，最终来说大的数据集都要分为小的数据集来进行处理。由此可以得到的改进就是，当数据集较小时，不必继续递归调用快速排序算法，而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成。Introsort就是这样的一种算法，它开始采用快速排序算法进行排序，当递归达到一定深度时就改为堆排序来处理。这样就克服了快速排序在小规模数据集处理中复杂的中轴选择，也确保了堆排序在最坏情况下O(n log n)的复杂度。  
    　　另一种优化改进是当分区的规模达到一定小时，便停止快速排序算法。也即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。数列中有部分元素并没有排到最终的有序序列的位置上，但是这种元素并不多。可以对这种“几乎”完成排序的数列使用插入排序算法进行排序以最终完成整个排序过程。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。  
    　　另一种快速排序的改进策略是在递归排序子分区的时候，总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。
 *  不同的分区方案考虑  
    　　对于快速排序算法来说，实际上大量的时间都消耗在了分区上面，因此一个好的分区实现是非常重要的。尤其是当要分区的所有的元素值都相等时，一般的快速排序算法就陷入了最坏的一种情况，也即反复的交换相同的元素并返回最差的中轴值。无论是任何数据集，只要它们中包含了很多相同的元素的话，这都是一个严重的问题，因为许多“底层”的分区都会变得完全一样。  
    　　对于这种情况的一种改进办法就是将分区分为三块而不是原来的两块：一块是小于中轴值的所有元素，一块是等于中轴值的所有元素，另一块是大于中轴值的所有元素。另一种简单的改进方法是，当分区完成后，如果发现最左和最右两个元素值相等的话就避免递归调用而采用其他的排序算法来完成。

# 2.插入类排序 #

## 2.1 直接插入排序 ##

*  **原理**：从待排序列的n个记录中的第二个记录开始。依次与前面的记录比较并寻找插入位置，寻找插入位置过程中顺便调整元素的位置。直到找到插入点，插入到适合的位置。
 *  **稳定性**：稳定排序
 *  **时间复杂度**： O ( n ) O(n) O(n)到 O （ n 2 ） O（n^2） O（n2）,平均时间复杂度为： O ( n 2 ) O(n^2) O(n2)
 *  **最好情况**：当待排序记录已经有序，这时需要比较的次数是 C m i n = n − 1 = O ( n ) C\_min=n-1=O(n) Cmin=n−1=O(n)。
 *  **最坏情况**：如果待排序记录为逆序，则最多的比较次数为： C m a x = ∑ i = 1 n − 1 i = n ( n − 1 ) 2 = O ( n 2 ) Cmax=\\sum\_\{i=1\}^\{n-1\}i=\\frac\{n(n-1)\}2=O(n^2) Cmax=∑i=1n−1i=2n(n−1)=O(n2)
 *  代码示例：

##插入排序
    arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    #第一种写法
    for i in range(1,len(arr)):
        key = arr[i]		#选取缓存值
        k = i-1
        while k>=0 and arr[k] > key:
                arr[k+1] = arr[k]
                k -= 1
        if k!=i-1: #防止自我插入
            arr[k+1]=key	#还原缓存值
    print(arr);

*  相应的java代码如下：

/** * 直接插入排序 * @param arr */
    public static void insertionSort(int[] arr){ 
    	for(int i=1;i<arr.length;i++){ 
    		int key = arr[i];   
    		int k=i-1;
    		//查找需要插入的位置
    		while(k>=0&&key <arr[k]){ 
    			arr[k+1]=arr[k];
    			k--;
    		}
    		if(k!=i-1){  //防止自我插入
    			arr[k+1]=key;
    		}
    	}
    }

*  插入排序的第二种种写法(python代码)：

##插入排序第二种写法
    arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    arr = [arr[0]] + arr
    for i in range(1,len(arr)):
        k = i-1
        arr[0] = arr[i]   #选取缓存值
        while arr[k]>arr[0]:
            arr[k+1] = arr[k]
            k -= 1
        arr[k+1] = arr[0]	#还原缓存值
    arr.pop(0)
    print(arr);

*  第二种写法的图形原理如图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMDg3OTU_size_16_color_FFFFFF_t_70]

## 2.2 shell排序（缩小增量排序） ##

*  shell排序又称**缩小增量排序**，由D.L.Shell在1959年提出，是对直接插入排序的改进。
 *  **原理**：Shell排序法是对相邻指定距离(称为增量)的元素进行比较，并不断把增量缩小至1，完成排序。
 *  Shell排序开始时增量较大，分组较多，每组的记录数目较少，故在各组内采用直接插入排序较快，后来增量di逐渐缩小，分组数减少，各组的记录数增多，但由于已经按di−1分组排序，文件叫接近于有序状态，所以新的一趟排序过程较快。因此Shell排序在效率上比直接插入排序有较大的改进。在直接插入排序的基础上，将直接插入排序中的1全部改变成增量d即可，因为Shell排序最后一轮的增量d就为1。
 *  **稳定性**：不稳定排序
 *  **时间复杂度**： O ( n 1.3 ) 到 O ( n 2 ) O(n^\{1.3\})到O(n^2) O(n1.3)到O(n2)。shell排序算法的实际复杂度分析比较复杂，实际所需的实际取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，shell排序的时间复杂度为 O ( n 1.3 ) O(n^\{1.3\}) O(n1.3)
 *  **对于增量的选择**：Shell 最初建议增量选择为n/2，并且对增量取半直到 1；D. Knuth教授建议di+1=⌊di−13⌋序列。  
    python代码如下：

##shell排序（缩小增量排序）
    arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    d = len(arr)
    while d>=1:
        d = d//2 #增量递减
        for icon in range(d,len(arr)):
            key = arr[icon] #设立缓存值
            i = icon-d
            while i>=0 and arr[i]>key:
                arr[i+d] = arr[i]
                i -= d   #每次减少一个增量
            if i+d!=icon: # 防止自我插入
                arr[i+d] = key #缓存值还原
    print(arr);

*  对应的java代码如下：

/** * shell排序，增量递减排序 * @param arr */
    public static void shellSort(int[] arr){ 
    	for(int d=arr.length/2;d>=1;d=d/2){ //d为增量，增量递减
    		for(int i = d;i<arr.length;i++){ 
    			int key = arr[i];	//记录缓存值
    			int j = i-d;
    			while( j >= 0 && arr[j]>key){ //寻找缓存值插入点
    				arr[j+d] = arr[j];
    				j -= d;
    			}
    			if(j+d!=i){  //防止自我插入
    				arr[j+d] = key;
    			}
    		}
    	}
    }

# 3.选择排序 #

## 3.1 简单选择排序（又称直接选择排序） ##

*  **原理**：从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。
 *  **稳定性**：不稳定排序。
 *  **时间复杂度**：最坏，最好和平均复杂度为 O ( n 2 ) O(n^2) O(n2),因此，简单选择排序也是常见排序算法中性能最差的排序算法。简单选择排序的比较次数与文件的初始状态没有关系，在第i趟选择排序中选出最小排序的记录，需要做n-i次的比较，因此总的比较次数是： ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) 2 = O ( n 2 ) \\sum\_\{i=1\}^\{n-1\}(n-i)=\\frac\{n(n-1)\}2=O(n^2) ∑i=1n−1(n−i)=2n(n−1)=O(n2)

#选择排序
    arr = [36,1,2,3,5,9,6,8,25,25,36,15,2,36,2,4,2,3,6,5,3,6,2,3,5,5,1]
    for i in range(0,len(arr)):
        key = i 
        for k in range(i+1,len(arr)):
            if arr[k]<arr[key] : 
                key = k  #记录最小值的索引
        if key!=i:  #防止自我插入
            arr[key],arr[i] = arr[i],arr[key]
    print(arr);

*  对应的java代码如下

/** * 选择排序 * @param arr */
    public static void optionSort(int[] arr){ 
    	for(int i =0;i<arr.length;i++){ 
    		int key = i; 
    		for(int k=i+1;k<arr.length;k++){ 
    			if(arr[key]>arr[k]){ 
    				key = k; //记录最小值的索引
    			}
    		}
    		if(key != i ){ 
    			//交换
    			arr[key] = arr[key]^arr[i];
    			arr[i] = arr[key]^arr[i];
    			arr[key] = arr[key]^arr[i];
    		}
    	}
    }

*  **选择排序优化**  
    每轮找出一个最大值，一个最小值。最大值放在最右边，最小值放在最左边。

##选择排序优化，每轮找出一个最大值，一个最小值。最大值放在最右边，最小值放在最左边。
    arr = [2,5,6,8,98,6,52,36,24,1,2,3,5,54,5]
    countlen = len(arr)
    for i in range(countlen//2):  #应为每轮选取为两个值一个放在最右边，一个放在最左边，所以只需要遍历到中间就已经排好序了。
        minindex = i
        oldmaxindex = -i-1
        maxindex = oldmaxindex
        for k in range(i+1,countlen-i): #定义无序区域
    # print(k,minindex,maxindex,countlen)
            if arr[k]<arr[minindex]: #最大值从右边向左寻找
                minindex = k
            if arr[-k-1]>arr[maxindex]: #最小值从左边向右寻找
                maxindex = -k-1
        if arr[maxindex]==arr[minindex]:break  # 如果最大值等于最小值。那么证明序列已经排序完成
        if minindex != i: #防止最小值自我插入
            arr[i],arr[minindex] = arr[minindex],arr[i]
            if maxindex == i: #纠正最大值下标
                maxindex = minindex;
        if maxindex != oldmaxindex and arr[maxindex] != arr[oldmaxindex]: # 防止最大值自我插入
            arr[-i-1],arr[maxindex] = arr[maxindex],arr[oldmaxindex]
    print(arr)

## 3.2 堆排序 ##

直接选择排序中，第一次选择经过了n-1次比较，只是从排序码序列中选出了一个最小的排序码，而没有保存其他中间比较结果。所以下一趟排序时又要重复许多比较操作，降低了效率。J. Willioms和Floyd在1964年提出了堆排序方法，避免这一缺点。  
**注意：学习堆排序前，请先了解[树的基本性质][Link 1]**

*  **堆的基本性质**

1.  堆在空间结构上复合完全二叉树
2.  堆排序中，需要先将完全二叉树调整为**大顶堆**或者**小顶堆**
    
     *  大顶堆：所有父结点的值都比其下的子节点的值要大。注意：大顶堆中，根结点一定是最大值。
     *  小顶堆：所有父结点的值都比其下的子节点的值要小。注意：小顶堆中，根结点一定是最小值。
3.  将待排序列与完全二叉树结构匹配。从根目录开始，从左到右，从上到下，对每一个完全二叉树的结点依次匹配数组中的元素。
    
     *  假定待排序列为：\[30,20,80,40,50,10,60,70,90\],对应结构如下：  
        ![sorttop10\_001][sorttop10_001]

*  **堆排序原理**

1.  将待排序列理解成一个完全二叉树，每一个元素与树的结点对应。那么最后一个元素一定是**最后一个结点**。最前面的一个元素一定是**根节点**。根据结点和树层数公式 i n t ( l o n g 2 ( n + 1 ) ) int(long\_2(n+1)) int(long2(n\+1))可以得到树的层数。
2.  调整待排序列构成的二叉树，使得完成二叉树构成一个**大顶堆**或者**小顶堆**，即可以从最后一个结点的父结(fnode = int(n/2))点开始依次向后调整。直到根结点为止。
    
     *  注意，为了满足大顶堆条件，将比较大的值放在父结点后，父结点原来的值会被下移到子节点。那么需要从新排断该子节点是否有自己的子节点。如果有，并且自己的子节点比自己大，那么数据依然需要下沉，知道比子节点大，或者没有子节点为止。
3.  由于大顶堆和小顶堆的出现，会得到一个极值(即：最大值，或者最小值)。将得到的极值放在有序区，脱离树，即原来的结点数变少，同时大顶堆或者小顶堆被打破规则。只需要从新调整改变的值所在大顶堆或者小顶堆的位置，即可重新是树恢复大顶堆和小顶堆的状态。依次循环，完成排序。

*  **稳定性**：不稳定排序
 *  **时间复杂度**：由于没次重新恢复堆的实际复杂度为 O ( l o n g N ) O(longN) O(longN),共N-1次调整操作，再加上前面建立堆时N/2次向下调，每次调整时间复杂度也为O(longN)。两次操作时间相加还是 O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN)。故堆排序的实际复杂度为： O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN).
 *  **最好情况**：如果待排序数组是有序的，仍然需要 O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN)复杂比较操作，只是少了移动的操作；
 *  **最坏情况**：如果待排序数组是逆序的，不仅需要 O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN)复杂比较操作，而且需要 O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN)复杂的交换操作。总的时间复杂度还是 O ( N ∗ l o n g N ) O(N\*longN) O(N∗longN)  
    因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是，数据的初始分布情况对堆排序的效率没有大的影响。  
    ![sorttop10\_010][sorttop10_010]
 *  **练习将一个数组打印成满二叉树**(可以跳过)
    
     *  可以帮助将平面结构的二叉树，空间结构化。帮助理解堆排序的动态效果
    
    1.  思路1，计算间隔空格，打印
    
        import math
        #思路1，计算间隔空格，打印
        def showtree(arr:list,unit_lenth:int=2 ,space:str=" "):
            hight = math.ceil(math.log2(len(arr)+1)) #完全二叉树层数
            index = 0
            for i in range(0,hight):
                temp = ((2**(hight-i)-1)*unit_lenth)
                end = index+2**i
                print((temp//2)*space + (temp*space).join(map(lambda x:"{:>{}}".format(x,unit_lenth),arr[index:end])))
                index = end
        arr = [_ for _ in range(20)]
        showtree(arr)
    
    ![sorttop10\_002][sorttop10_002]  
    2. 思路2，居中对齐打印
    
        import math,random
        #思路2，居中对齐打印
        def showtree(arr:list,unit_lenth:int=1 ,space:str=" "):
            hight = math.ceil(math.log2(len(arr)+1)) #完全二叉树层数
            index = 0
            width = (2**hight-1)*unit_lenth
            for i in range(0,hight):
                end = index+2**i
                for k in arr[index:end]:
                    print("{:^{}}".format(k,width),sep="",end=space*unit_lenth)
                print()
                width //=2
                index = end
        arr = [random.randint(0,9) for _ in range(40)]
        showtree(arr)
    
    ![sorttop10\_003][sorttop10_003]  
    3. 和思路1类似，计算间隔空格，打印
    
        #和思路1类似，计算间隔空格，打印
        import math
        arr = [_ for _ in range(1,20)]
        def showtree(arr,unit:int=2):
            length = len(arr) #节点数
            height = math.ceil(math.log2(length+1)) #树的层数
            index = 0
            for i in range(height):
                hgcount = int(math.pow(2,i)) #每层的个数
                temp = int(math.pow(2,height-i-1)-1)
                temp2 = 2*temp+1
                for k in range(hgcount):
                    print(" "*unit * (temp2 if k else temp),"{:>{}}".format(arr[index],unit),end="",sep="")
                    index += 1
                    if index>=length:
                        print()
                        return
                print()
        showtree(arr)
    
    ![sorttop10\_004][sorttop10_004]
 *  **堆排序实现**

1.  python代码如下：

import math
    arr = [10,30,50,60,2,5,6,80]
    #为大顶堆调整单个结点
    def updatenode(node,fnode,arr:list):#node 结点数，fnode需要调整的结点，arr数组
        leftnode = fnode*2 #计算左结点
        while leftnode<=node: #存在左结点
            maxnode = leftnode #假定左结点值是最大值
            rightnode = leftnode+1 #定义又结点
            if rightnode<=node and arr[rightnode]>arr[maxnode]:
                maxnode = rightnode
            if arr[maxnode]>arr[fnode]:#如果父结点不是最大值，调整结点
                arr[fnode],arr[maxnode] = arr[maxnode],arr[fnode]
                fnode = maxnode
                leftnode = fnode*2 #计算左结点
            else:
                break #父结点已经是最大值，则完成调整
    #堆排序
    def souretruee(arr:list):    
        #开始位置添加一个元素，方便计算结点
        arr.append(arr[0])
        arr[0] = 0
        nodecount = len(arr)-1 #节点数
        #构建大顶堆
        for i in range(nodecount//2,0,-1):
            updatenode(nodecount,i,arr)
        while nodecount>=3:
            #获取已经出现的最大值，打乱大顶堆
            arr[1],arr[nodecount] = arr[nodecount],arr[1] 
            nodecount -= 1
            #调整大顶堆
            updatenode(nodecount,1,arr)
        if nodecount==2 and arr[1]>arr[2]:
            arr[1],arr[2] = arr[2],arr[1]
        #删除添加的多余元素
        arr[:] = arr[1:]
        return arr
    
    # showtree(arr)
    print(souretruee(arr))
    # print(arr)

上面代码中，是使用大顶堆的逆向向上调整思路，最近看到一个小顶堆顺向向上调整代码。如下所示：也是一种新的思路。

*  一种新思路的小顶堆调整。顺向向上调整。

#调整新加入的元素，实现小顶堆。(向上调整小顶堆)
    def minHeapFixUp(arr,i):# arr数组，i插入的新元素索引
        temp = arr[i] #记录缓存值，新添加的元素
        j = (i-1)//2 #父结点
        while j>=0 and i!=0:
            if arr[j] <= temp: break #如果父结点，比新插入的元素小，停止寻找插入位置。
            arr[i] = arr[j] #下移大的子节点
            i = j
            j = (i-1)//2
        arr[i] = temp #找到适合位置，插入元素，使得数组满足小顶堆
    #调整小顶堆代码
    def getmintenode(arr:list):
        for k in range(1,len(arr)):
            minHeapFixUp(arr,k)
            
    arr = [10,20,50,90,30,40,80,60,70,20,30]
    showtree(arr)
    print("- "*30)
    getmintenode(arr)
    showtree(arr)

![sorttop10\_005][sorttop10_005]

1.  使用java实现堆排序

### 堆排序图解： ###

1.  原序列：  
    ![sorttop10\_006][sorttop10_006]
2.  构建大顶堆后：  
    ![sorttop10\_007][sorttop10_007]
3.  堆顶和最后一个结点交换，并排除最后一个结点  
    ![sorttop10\_008][sorttop10_008]
4.  依次排序过程：  
    ![sorttop10\_009][sorttop10_009]

# 4.归并类排序 #

## 4.1 归并排序 ##

*  对应的java代码

# 5.线性时间非比较类排序 #

## 5.1 计数排序 ##

*  对应的java代码

## 5.2 基数排序 ##

*  对应的java代码

## 5.3 桶排序 ##

*  对应的java代码

参考文献：[https://blog.csdn.net/coolwriter/article/details/78732728][https_blog.csdn.net_coolwriter_article_details_78732728]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwMDg3OTU_size_16_color_FFFFFF_t_70]: /images/20220228/cabca109097347fa84238ae5837de938.png
[Link 1]: https://blog.csdn.net/u013008795/article/details/89375597
[sorttop10_001]: https://raw.githubusercontent.com/1263351411/xdd.github.io/master/img/python/sorttop10_001.jpg
[sorttop10_010]: https://raw.githubusercontent.com/1263351411/xdd.github.io/master/img/python/sorttop10_010.jpg
[sorttop10_002]: /images/20220228/83a445512f064d7d9fb619fcc995d369.png
[sorttop10_003]: /images/20220228/8b366aea95254525b32538c405a94bdc.png
[sorttop10_004]: /images/20220228/593f08378392477eaafceac1e5d95104.png
[sorttop10_005]: /images/20220228/954282b2d836408995d215e8437b989b.png
[sorttop10_006]: /images/20220228/c2a60c49daa94febb22ae5d820a8e74c.png
[sorttop10_007]: /images/20220228/f83871104d2e41838d92b9f66f6205e0.png
[sorttop10_008]: /images/20220228/71b9bfa33b1a4cd2ac4f7765da95b10a.png
[sorttop10_009]: /images/20220228/cad27ec82f9548da8f5b291137fb56ce.png
[https_blog.csdn.net_coolwriter_article_details_78732728]: https://blog.csdn.net/coolwriter/article/details/78732728