go语言实现7大排序算法

代码示例评论阅读8分2秒

以下是七大排序算法的基本思想以及相应的Go语言实现:

文章源自Golang编程指南-https://www.va26.com/work/313.html

冒泡排序(Bubble Sort):文章源自Golang编程指南-https://www.va26.com/work/313.html

基本思想:通过重复遍历待排序的列表,比较相邻的两个元素,如果它们的顺序错误就交换它们,直到没有元素需要交换为止。文章源自Golang编程指南-https://www.va26.com/work/313.html

func bubbleSort(arr []int) {  
    n := len(arr)  
    for i := 0; i < n-1; i++ {  
        for j := 0; j < n-i-1; j++ {  
            if arr[j] > arr[j+1] {  
                // 交换元素  
                arr[j], arr[j+1] = arr[j+1], arr[j]  
            }  
        }  
    }  
}

选择排序(Selection Sort):文章源自Golang编程指南-https://www.va26.com/work/313.html

基本思想:在未排序的序列中找到最小(或最大)的元素,存放到排序序列的起始位置,然后再从剩余未排序的元素中继续寻找最小(或最大)元素,然后放到已排序的序列的末尾。文章源自Golang编程指南-https://www.va26.com/work/313.html

func selectionSort(arr []int) {  
    n := len(arr)  
    for i := 0; i < n-1; i++ {  
        minIndex := i  
        for j := i + 1; j < n; j++ {  
            if arr[j] < arr[minIndex] {  
                minIndex = j  
            }  
        }  
        // 交换位置  
        arr[i], arr[minIndex] = arr[minIndex], arr[i]  
    }  
}

插入排序(Insertion Sort):文章源自Golang编程指南-https://www.va26.com/work/313.html

基本思想:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。文章源自Golang编程指南-https://www.va26.com/work/313.html

func insertionSort(arr []int) {  
    n := len(arr)  
    for i := 1; i < n; i++ {  
        key := arr[i]  
        j := i - 1  
        for j >= 0 && arr[j] > key {  
            arr[j+1] = arr[j]  
            j = j - 1  
        }  
        arr[j+1] = key  
    }  
}

希尔排序(Shell Sort):文章源自Golang编程指南-https://www.va26.com/work/313.html

基本思想:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行一次直接插入排序。文章源自Golang编程指南-https://www.va26.com/work/313.html

func shellSort(arr []int) {  
    n := len(arr)  
    gap := n / 2  
    for gap > 0 {  
        for i := gap; i < n; i++ {  
            temp := arr[i]  
            j := i  
            for j >= gap && arr[j-gap] > temp {  
                arr[j] = arr[j-gap]  
                j -= gap  
            }  
            arr[j] = temp  
        }  
        gap /= 2  
    }  
}1

快速排序(Quick Sort):文章源自Golang编程指南-https://www.va26.com/work/313.html

基本思想:通过一次排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行。

func quickSort(arr []int, low, high int) {  
    if low < high {  
        pi := partition(arr, low, high)  
        quickSort(arr, low, pi-1)  
        quickSort(arr, pi+1, high)  
    }  
}  
  
func partition(arr []int, low, high int) int {  
    pivot := arr[high]  
    i := low - 1  
    for j := low; j < high; j++ {  
        if arr[j] < pivot {  
            i++  
            arr[i], arr[j] = arr[j], arr[i]  
        }  
    }  
    arr[i+1], arr[high] = arr[high], arr[i+1]  
    return i + 1  
}

归并排序(Merge Sort):

基本思想:采用分治的思想,将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

func mergeSort(arr []int, low, mid, high int) {  
    if low < high {  
        mergeSort(arr, low, (low+high)/2, high)  
        merge(arr, low, (low+high)/2, high)  
    }  
}  
  
func merge(arr []int, low, mid, high int) {  
    n1 := mid - low + 1  
    n2 := high - mid  
    left := make([]int, n1)  
    right := make([]int, n2)  
    copy(left, arr[low:mid+1])  
    copy(right, arr[mid+1:high+1])  
    i := 0  
    j := 0  
    k := low  
    for i < n1 && j < n2 {  
        if left[i] <= right[j] {  
            arr[k] = left[i]  
            i++  
        } else {  
            arr[k] = right[j]  
            j++  
        }  
        k++  
    }  
    for i < n1 {  
        arr[k] = left[i]  
        i++  
        k++  
    }  
    for j < n2 {  
        arr[k] = right[j]  
        j++  
        k++  
    }  
}

堆排序(Heap Sort):

基本思想:利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

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

以上代码示例为简化版本,可能需要根据实际需求进一步优化和调整。在实际应用中,通常需要考虑更多的边界条件和错误处理。为了保持代码的可读性和可维护性,建议对函数和变量使用描述性的命名,并添加必要的注释说明。

 
  • 本文由golang编程指南作者原创,请勿恶意转载!
  • 转载请务必保留本文链接:https://www.va26.com/work/313.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证