如何对数组进行排序

数组排序

数组排序是指将一组数据按照某种顺序进行排列，以便更容易查找和比较。数组排序可以有效地提高程序的性能，并且可以帮助程序员更好地理解程序的运行过程。

常用的数组排序方法

常用的数组排序方法有冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

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

选择排序

选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

func selectSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        minIndex := i
        for j := i + 1; j < length; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
    return arr
}

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

func insertSort(arr []int) []int {
    length := len(arr)
    for i := 1; i < length; i++ {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex--
        }
        arr[preIndex+1] = current
    }
    return arr
}

快速排序

快速排序是一种分治算法，它将一个数组分成两个子数组，将两部分独立排序。快速排序的主要思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比一部分的所有数据都要小，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid, i := arr[0], 1
    head, tail := 0, len(arr)-1
    for head < tail {
        if arr[i] > mid {
            arr[i], arr[tail] = arr[tail], arr[i]
            tail--
        } else {
            arr[i], arr[head] = arr[head], arr[i]
            head++
            i++
        }
    }
    arr[head] = mid
    quickSort(arr[:head])
    quickSort(arr[head+1:])
    return arr
}

归并排序

归并排序是一种分治算法，它将一个数组分成两个子数组，将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。再把有序子序列合并为整体有序序列。

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    num := len(arr) / 2
    left := mergeSort(arr[:num])
    right := mergeSort(arr[num:])
    return merge(left, right)
}