算法基础——十大排序

怼烎@ 2023-01-13 10:57 164阅读 0赞

### 文章目录 ###

*   *   *  十大排序算法对比
         *   *  名词解释
         *  冒泡排序
         *  选择排序
         *  插入排序
         *  希尔排序
         *  归并排序
         *  快速排序
         *  堆排序
         *  计数排序
         *  桶排序
         *  基数排序

### 十大排序算法对比 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQxNDAyNQ_size_16_color_FFFFFF_t_70]

#### 名词解释 ####

*  n：数据规模
 *  k："桶"的个数
 *  In-place：占用常数内存，不占用额外内存
 *  Out-place：占用额外内存
 *  稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

### 冒泡排序 ###

*  算法介绍  
    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 *  算法描述  
    1，比较相邻的元素。如果第一个比第二个大，就交换它们两个；  
    2，对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；  
    3，针对所有的元素重复以上的步骤，除了最后一个；  
    4，重复步骤1~3，直到排序完成。
 *  代码  
    基础版本

package SortAlgorithm
    
    func BubbleSort(arr []int){
        
    	for i := 0; i < len(arr)-1; i++ {
        
    		for j := 0; j < len(arr)-1-i; j++ {
        
    			if arr[j] > arr[j+1] {
        
    				arr[j], arr[j+1] = arr[j+1], arr[j]
    			}
    		}
    	}
    }

递归版本

func BubbleRecursion(arr []int, left, right int) {
        
    	if right == 0 {
        
    		return
    	}
    	for index, num := range arr {
        
    		if index < right && num > arr[index+1] {
        
    			arr[index], arr[index+1] = arr[index+1], arr[index]
    		}
    	}
    	BubbleRecursion(arr, left, right-1)
    }

### 选择排序 ###

*  算法介绍  
    选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
 *  算法描述  
    1,首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。  
    再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。  
    重复第二步，直到所有元素均排序完毕。

package SortAlgorithm
    
    func SelectionSort(arr []int) []int {
        
    	length := len(arr)
    	for i := 0; i < length-1; i++ {
        
    		min := i
    		for j := i + 1; j < length; j++ {
        
    			if arr[min] > arr[j] {
        
    				min = j
    			}
    		}
    		arr[i], arr[min] = arr[min], arr[i]
    	}
    	return arr
    }

### 插入排序 ###

*  算法介绍  
    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
 *  算法描述

package SortAlgorithm
    
    func InsertionSort(arr []int) []int {
        
    	for i, current := range arr {
        
    		preIndex := i - 1
    		for preIndex >= 0 && arr[preIndex] > current {
         //判断前项是否比要插入的数字大
    			arr[preIndex+1] = arr[preIndex] //将前项往后移
    			preIndex -= 1                   //继续往前找合适插入的位置
    		}
    		arr[preIndex+1] = current //如果前项不比要排序的数字大，即找到了合适的位置插入，则插入到前项的后面
    	}
    	return arr
    }

![在这里插入图片描述][20210422113842635.gif]

### 希尔排序 ###

*  算法介绍：  
    希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
 *  算法描述  
    希尔排序是基于插入排序的以下两点性质而提出改进方法的：  
    1，插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；  
    2，但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；  
    希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
 *  代码

func ShellSort(arr []int) []int {
        
            length := len(arr)
            gap := 1
            for gap < gap/3 {
        
                    gap = gap*3 + 1
            }
            for gap > 0 {
        
                    for i := gap; i < length; i++ {
        
                            temp := arr[i]
                            j := i - gap
                            for j >= 0 && arr[j] > temp {
        
                                    arr[j+gap] = arr[j]
                                    j -= gap
                            }
                            arr[j+gap] = temp
                    }
                    gap = gap / 3
            }
            return arr
    }

### 归并排序 ###

*  算法介绍  
    归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
 *  算法描述  
    1， 算法步骤  
    申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；  
    2，设定两个指针，最初位置分别为两个已经排序序列的起始位置；  
    3，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；  
    4，重复步骤 3 直到某一指针达到序列尾；  
    5，将另一序列剩下的所有元素直接复制到合并序列尾![在这里插入图片描述][20210423100129436.gif]
 *  代码

package SortAlgorithm
    
    func MergeSort(arr []int) []int {
        
    	length := len(arr)
    	if length < 2 {
        
    		return arr
    	}
    	middle := length / 2
    	left := arr[0:middle]
    	right := arr[middle:]
    	return merge(MergeSort(left), MergeSort(right))
    }
    
    func merge(left []int, right []int) []int {
        
    	var result []int
    	for len(left) != 0 && len(right) != 0 {
        
    		if left[0] <= right[0] {
        
    			result = append(result, left[0])
    			left = left[1:]
    		} else {
        
    			result = append(result, right[0])
    			right = right[1:]
    		}
    	}
    
    	for len(left) != 0 {
        
    		result = append(result, left[0])
    		left = left[1:]
    	}
    
    	for len(right) != 0 {
        
    		result = append(result, right[0])
    		right = right[1:]
    	}
    
    	return result
    }

### 快速排序 ###

*  算法介绍  
    快速排序采用了二分递归的思想，通过一趟排序将整个数组划分为两个部分，低位部分的值全部小于高位部分的值，然后对低位和高位部分分别排序
 *  算法步骤  
    1 ，从数列中挑出一个元素，称为 “基准”（pivot）;  
    2 ，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；  
    3 ，递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；  
    ![在这里插入图片描述][20210423141705345.gif]
 *  代码

func partition(arr *[]int,left int,right int)int{
        
    	privot:=(*arr)[right]
    	i:=left-1
    	for j:=left;j<right;j++{
        
    		if (*arr)[j]<privot{
        
    			i++
    			temp:=(*arr)[i]
    			(*arr)[i]=(*arr)[j]
    			(*arr)[j]=temp
    		}
    	}
    	temp:=(*arr)[i+1]
    	(*arr)[i+1]=(*arr)[right]
    	(*arr)[right]=temp
    	return i+1
    }
    //递归
    func QuickSort(arr *[]int,left int,right int){
        
    	if left>= right{
        
    		return
    	}
    	privot:=partition(arr,left,right)
    	QuickSort(arr,left,privot-1)
    	QuickSort(arr,privot+1,right)
    }

### 堆排序 ###

*  算法介绍  
    堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
 *  算法步骤  
    1， 创建一个堆 H\[0……n-1\]  
    2， 把堆首（最大值）和堆尾互换；  
    3， 把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置；  
    4， 重复步骤 2，直到堆的尺寸为 1
 *  算法代码

func heapSort(arr []int) []int {
        
            arrLen := len(arr)
            buildMaxHeap(arr, arrLen)
            for i := arrLen - 1; i >= 0; i-- {
        
                    swap(arr, 0, i)
                    arrLen -= 1
                    heapify(arr, 0, arrLen)
            }
            return arr
    }
    
    func buildMaxHeap(arr []int, arrLen int) {
        
            for i := arrLen / 2; i >= 0; i-- {
        
                    heapify(arr, i, arrLen)
            }
    }
    
    func heapify(arr []int, i, arrLen int) {
        
            left := 2*i + 1
            right := 2*i + 2
            largest := i
            if left < arrLen && arr[left] > arr[largest] {
        
                    largest = left
            }
            if right < arrLen && arr[right] > arr[largest] {
        
                    largest = right
            }
            if largest != i {
        
                    swap(arr, i, largest)
                    heapify(arr, largest, arrLen)
            }
    }
    
    func swap(arr []int, i, j int) {
        
            arr[i], arr[j] = arr[j], arr[i]
    }

### 计数排序 ###

*  算法介绍  
    计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上  
    ![在这里插入图片描述][20210423150705201.gif]
 *  算法步骤  
    （1）找出待排序的数组中最大和最小的元素  
    （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项  
    （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）  
    （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
 *  代码

package SortAlgorithm
    func CountingSort(arr []int, maxValue int) []int {
        
    	bucketLen := maxValue + 1
    	bucket := make([]int, bucketLen) // 初始为0的数组
    
    	sortedIndex := 0
    	length := len(arr)
    
    	for i := 0; i < length; i++ {
        
    		bucket[arr[i]] += 1
    	}
    
    	for j := 0; j < bucketLen; j++ {
        
    		for bucket[j] > 0 {
        
    			arr[sortedIndex] = j
    			sortedIndex += 1
    			bucket[j] -= 1
    		}
    	}
    
    	return arr
    }

### 桶排序 ###

*  算法介绍  
    桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序
 *  代码

func bucketSort(theArray []int,num int){
        
    	var theSort [99]int
    	for i:=0;i< len(theArray);i++{
        
    		theSort[10]=1
    		if theSort[theArray[i]] !=0{
        
    			theSort[theArray[i]] = theSort[theArray[i]]+1
    		}else{
        
    			theSort[theArray[i]] = 1
    		}
    	}
    	l:=list.New()
    	for j:=0;j<len(theSort);j++{
        
    		if theSort[j]==0{
        
    			//panic("error test.....")
    		}else{
        
    			for k:=0;k<theSort[j];k++{
        
    				l.PushBack(j)
    			}
    		}
    	}
    	for e := l.Front(); e != nil; e = e.Next() {
        
    		fmt.Print(e.Value, " ")
    	}
     
    }

### 基数排序 ###

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

*  代码

//获取数组的最大值
    func maxValue(arr []int)(ret int){
        
        ret =1
    var key int=10
    for i :=0; i < len(arr); i++{
        
    for arr[i]>= key {
        
                key = key *10
                ret++
    }
    }
    return
    }
    func radixSort(arr []int){
        
        key := maxValue(arr)
        tmp := make([]int, len(arr), len(arr))
        count :=new([10]int)
        radix :=1
    var i, j, k int
    for i =0; i < key; i++{
        //进行key次排序
    for j =0; j <10; j++{
        
                count[j]=0
    }
    for j =0; j < len(arr); j++{
        
                k =(arr[j]/ radix)%10
                count[k]++
    }
    for j =1; j <10; j++{
        //将tmp中的为准依次分配给每个桶
                count[j]= count[j-1]+ count[j]
    }
    for j = len(arr)-1; j >=0; j--{
        
                k =(arr[j]/ radix)%10
                tmp[count[k]-1]= arr[j]
                count[k]--
    }
    for j =0; j <len(arr); j++{
        
                arr[j]= tmp[j]
    }
            radix = radix *10
    }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQxNDAyNQ_size_16_color_FFFFFF_t_70]: /images/20221022/cc48170847d74a9a80386f804dc575b9.png
[20210422113842635.gif]: /images/20221022/8c17449e707e4a42bff1d9b0f265282f.png
[20210423100129436.gif]: /images/20221022/08627c8d096d497ca7ac4edc210cb1f8.png
[20210423141705345.gif]: /images/20221022/1c7d03e2971f482084de67357ff5adc7.png
[20210423150705201.gif]: /images/20221022/15ef50ac7c514f9596af23d9f2d35338.png