十大排序算法

算法说明

十大排序算法分别是：

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序

Python版本

#!/usr/bin/python
# coding=utf-8


import sys
import os
import math

def bubbleSort(arr):
    '''
    冒泡排序
    '''
    length = len(arr)
    if length < 2:
        return arr

    for i in range(1, length, 1):
        for j in range(0, length-i, 1):
            if arr[j] > arr[j+1]:
                # arr[j],arr[j+1] = arr[j+1],arr[j]
                arr[j] = arr[j] + arr[j+1]
                arr[j+1] = arr[j] - arr[j+1]
                arr[j] = arr[j] - arr[j+1]
    # print("冒泡排序：" + str(arr))
    print("bubbleSort：" + str(arr))
    return arr

def selectSort(arr):
    '''
    选择排序
    '''
    length = len(arr)
    if length < 2:
        return arr

    for i in range(0, length):
        index = i
        for j in range(i+1, length):
            if arr[j] < arr[index]:
                index = j
        if index != i:
            arr[i],arr[index] = arr[index],arr[i]
    # print("选择排序：" + str(arr))
    print("selectSort：" + str(arr))
    return arr

def insertSort(arr):
    '''
    插入排序
    '''
    length = len(arr)
    if length < 2:
        return arr

    gap = 1
    for i in range(0, length):
        index = i-gap
        value = arr[i]
        while index >= 0:
            if arr[index] > value:
                arr[index+1] = arr[index]
                index -= 1
            else:
                break
        # while index >= 0 and arr[index] > value:
        #   arr[index+1] = arr[index]
        #   index -= 1
        arr[index+1] = value
    # print("插入排序：" + str(arr))
    print("insertSort：" + str(arr))
    return arr

def shellSort(arr):
    '''
    希尔排序
    '''
    lenght = len(arr)
    if lenght < 2:
        return arr

    gap = lenght//2
    while gap > 0:
        for i in range(0,lenght):
            index = i - gap
            value = arr[i]
            while index >= 0 and arr[index]>value:
                arr[index+gap] = arr[index]
                index -= gap
            arr[index+gap] = value
        gap = gap//2
    # print("希尔排序：" + str(arr))
    print(" shellSort：" + str(arr))
    return arr

def mergeSort(arr):
    '''
    归并排序
    '''
    def mergeData(left,right):
        result = []
        while len(left)>0 and len(right):
            if left[0] > right[0]:
                result.append(right.pop(0))
            else:
                result.append(left.pop(0))
        while len(left)>0:
            result.append(left.pop(0))
        while len(right)>0:
            result.append(right.pop(0))
        return result
    
    def devide(arr):
        length = len(arr)
        if length < 2:
            return arr
        middle = length//2
        left = arr[0:middle]
        right = arr[middle:length]
        return mergeData(devide(left),devide(right))

    length = len(arr)
    if length < 2:
        return arr
    result = devide(arr)
    # print("归并排序：" + str(result))
    print(" mergeSort：" + str(result))
    return result

def quickSort(arr):
    '''
    快速排序
    '''
    def pivotSort(arr,start,end):
        pivotValue = arr[end]
        index = start
        j = start
        while j < end:
            if arr[j] < pivotValue:
                arr[index],arr[j] = arr[j],arr[index]
                index += 1
            j += 1
        arr[index],arr[end] = arr[end],arr[index]
        return index

    def pivotSort2(arr,start,end):
        pivot = arr[start]
        while start < end:
            while start < end and arr[end] > pivot:
                end -= 1
            arr[start] = arr[end]
            while start < end and arr[start] <= pivot:
                start += 1
            arr[end] = arr[start]
        arr[start] = pivot
        return start

    def quickSortStart(arr,start,end):
        if start < end:
            # pivotIndex = pivotSort(arr,start,end)
            pivotIndex = pivotSort2(arr,start,end)
            quickSortStart(arr,start,pivotIndex-1)
            quickSortStart(arr,pivotIndex+1,end)
        return arr

    length = len(arr)
    if length < 2:
        return arr
    result = quickSortStart(arr,0,len(arr)-1)
    # print("快速排序：" + str(result))
    print(" quickSort：" + str(result))
    return result

def heapSort(arr):
    '''
    堆排序
    '''
    arrLength = len(arr)
    if arrLength < 2:
        return arr

    def swap(arr,i,j):
        arr[i],arr[j] = arr[j],arr[i]

    def heapify(arr,i):
        left = 2*i + 1
        right = 2*i + 2
        largest = i
        if left < arrLength and arr[left] > arr[largest]:
            largest = left
        if right < arrLength and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            swap(arr,i,largest)
            heapify(arr,largest)

    def buildMaxHeap(arr):
        # for i in range(math.floor(len(arr)/2),-1,-1):
        for i in range(len(arr)/2,-1,-1):
            heapify(arr,i)

    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLength -= 1
        heapify(arr,0)
    # print("    堆排序：" + str(arr))
    print("  heapSort：" + str(arr))
    return arr

def countSort(arr):
    '''
    计数排序
    '''
    arrLength = len(arr)
    if arrLength < 2:
        return arr

    minValue = 0
    maxValue = 0
    for item in arr:
        minValue = min(minValue,item)
        maxValue = max(maxValue,item)
    # 计算得到临时数组的长度
    bucketLen = (maxValue - minValue) + 1
    # 初始化临时数组
    bucket = [0 for i in range(bucketLen)]
    # 源数组的值为key，出现次数为value存储到临时数组
    for item in arr:
        bucket[item-minValue] += 1
    # 新建结果数组
    result = [0 for i in range(arrLength)]
    index = 0
    for i in range(0,bucketLen):
        while bucket[i] > 0:
            result[index] = i+minValue
            index += 1
            bucket[i] -= 1
    # print("  计数排序：" + str(result))
    print(" countSort：" + str(result))
    return result

def bucketSort(arr):
    '''
    桶排序
    '''
    arrLength = len(arr)
    if arrLength < 2:
        return arr
    minValue = 0
    maxValue = 0
    for item in arr:
        minValue = min(minValue,item)
        maxValue = max(maxValue,item)
    # 计算得到桶数量
    bucketNum = (maxValue - minValue)/arrLength + 1
    # 初始化桶
    # bucket = [[]]*n操作中，只是创建n个指向list的引用，一旦list改变，bucket中n个list也会随之改变。
    # 需要使用间接定义的方式创建二维数组
    bucket = [[] for i in range(bucketNum)]
    # 将源数组的元素放入各个桶中
    for item in arr:
        num = (item - minValue)/arrLength
        currentBucket = bucket[num]
        currentBucket.append(item)
    # 各个桶中元素排序
    for item in bucket:
        quickSort(item)
    # 获取所有桶排序后的数据
    index = 0
    for item in bucket:
        for value in item:
            arr[index] = value
            index += 1
    print("bucketSort：" + str(arr))
    return arr

def radixSort(arr):
    '''
    基数排序
    '''
    arrLength = len(arr)
    if arrLength < 2:
        return arr
    def getMax(arr):
        maxValue = arr[0]
        for item in arr:
            maxValue = max(item,maxValue)
        return maxValue

    def digitsCountSort(arr,exp):
        # 存储"被排序数据"的临时数组
        output = [0 for i in range(arrLength)]
        # 每一位的数字只能是[0-9)，所以默认新建长度为10的数组
        bucket = [0 for i in range(10)]
        # 源数组当前为数的值为key，出现次数为value存储到临时数组
        for i in range(0,arrLength):
            num = (arr[i]/exp)%10
            bucket[num] += 1
        # 这里修改后使得buckets[i]的值就是排序后该数据在源数组中应处的位置
        for i in range(1,10):
            bucket[i] += bucket[i-1]
        # 将数据存储到临时数组output[]中
        for i in range(arrLength-1,-1,-1):
            num = (arr[i]/exp)%10
            output[bucket[num]-1] = arr[i]
            bucket[num] -= 1
        # 将排序好的数据赋值给a[]
        for i in range(0,arrLength):
            arr[i] = output[i]

    maxValue = getMax(arr)
    # 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
    exp = 1
    while maxValue/exp > 0:
        #从个位数开始，对数组按exp位数进行桶排序
        digitsCountSort(arr,exp)
        exp = exp * 10
    print(" radixSort：" + str(arr))
    return arr

Swift版本

class Sort: NSObject {
    
    /// 冒泡排序
    static func bubbleSort(_ data:Array<Int>)->Any{
        var dataAry:Array<Int> = data
        let num = dataAry.count - 1
        if num < 1 {
            return dataAry
        }
        for i in 1...num {
            for j in 0...(num-i) {
                if dataAry[j] > dataAry[j+1] {
                    let temp = dataAry[j+1]
                    dataAry[j+1] = dataAry[j]
                    dataAry[j] = temp
                }
            }
        }
        print("冒泡排序：",dataAry)
        return dataAry
    }
    
    /// 选择排序
    static func selectSort(_ data:Array<Int>)->Any {
        var dataAry:Array<Int> = data
        let num = dataAry.count - 1
        if num < 1 {
            return dataAry
        }
        
        for i in 0...num-1 {
            var index:Int = i
            for j in i+1...num {
                if dataAry[j] < dataAry[index] {
                    index = j
                }
            }
            if index != i {
                let temp = dataAry[i]
                dataAry[i] = dataAry[index]
                dataAry[index] = temp
            }
        }
        print("选择排序：",dataAry)
        return dataAry
    }
    
    /// 插入排序
    static func insertSort(_ data:Array<Int>) -> Any {
        var dataAry:Array<Int> = data
        let num = dataAry.count - 1
        if num < 1 {
            return dataAry
        }
        for i in 0...num {
            let value = dataAry[i]
            var index = i-1
            while index >= 0 {
                if dataAry[index] > value {
                    dataAry[index+1] = dataAry[index]
                    index -= 1
                }else{
                    break
                }
            }
            dataAry[index+1] = value
        }
        print("插入排序：",dataAry)
        return dataAry
    }
    
    /// 希尔排序
    static func shellSort(_ data:Array<Int>)->Any {
        var dataAry:Array<Int> = data
        let num = data.count - 1
        if num < 1 {
            return dataAry
        }
        var gap = num/2
        while gap > 0 {
            for i in 0...num {
                let value = dataAry[i]
                var index = i - gap
                while index >= 0 {
                    if dataAry[index] > value {
                        dataAry[index+gap] = dataAry[index]
                        index -= gap
                    }else{
                        break
                    }
                }
                dataAry[index+gap] = value
            }
            gap = gap/2
        }
        print("希尔排序：",dataAry)
        return dataAry
    }
    
    /// 归并排序
    static func mergeSort(_ data:Array<Int>)->Any {
        let dataAry:Array<Int> = data
        let num = data.count - 1
        if num < 1 {
            return dataAry
        }
        
        func mergeData(_ left:Any, _ right:Any)->Any {
            var result:Array<Int> = []
            var leftData:Array<Int> = left as! Array<Int>
            var rightData:Array<Int> = right as! Array<Int>
            while leftData.count > 0 && rightData.count > 0 {
                if leftData[0] > rightData[0] {
                    result.append(rightData.first!)
                    rightData.remove(at: 0)
                }else{
                    result.append(leftData.first!)
                    leftData.remove(at: 0)
                }
            }
            while leftData.count > 0 {
                result.append(leftData.first!)
                leftData.remove(at: 0)
            }
            while rightData.count > 0 {
                result.append(rightData.first!)
                rightData.remove(at: 0)
            }
            return result
        }
        
        func devideData(_ array:Array<Int>)->Any {
            if array.count < 2 {
                return array
            }
            let middle = array.count/2
            var left:Array<Int> = []
            var right:Array<Int> = []
            for i in 0...(array.count-1) {
                if i < middle {
                    left.append(array[i])
                }else{
                    right.append(array[i])
                }
            }
            return mergeData(devideData(left),devideData(right))
        }
        
        let result = devideData(dataAry)
        print("归并排序：",result)
        return result
    }
    
    /// 快速排序
    static func quickSort(_ data:Array<Int>)->Any {
        let num = data.count - 1
        if num < 1 {
            return data
        }
        
        func swap(data: inout Array<Int>, i:Int, j:Int) {
            let temp = data[i]
            data[i] = data[j]
            data[j] = temp
        }
        //挖坑法
        func findPoint(result: inout Array<Int>, start:Int, end:Int)->Int {
            let value = result[start]
            var left = start
            var right = end
            while left < right {
                while left < right && result[right] > value {
                    right -= 1
                }
                result[left] = result[right]
                while left < right && result[left] <= value {
                    left += 1
                }
                result[right] = result[left]
            }
            result[left] = value
            return left
        }
        //前后指针法
        func findPoint2(result: inout Array<Int>, start:Int, end:Int)->Int {
            //取队尾为桩
            let value = result[end]
            var i = start
            var index = start
            while i < end {
                if result[i] < value {
                    swap(data: &result, i: i, j: index)
                    index += 1
                }
                i += 1
            }
            swap(data: &result, i: end, j: index)
            return index
            
//            //取队头为桩
//            let pivot = result[start]
//            var index = start + 1
//            var i = index
//            while  i <= end {
//                if result[i] < pivot {
//                    swap(data:&result, i:i, j:index)
//                    index += 1
//                }
//                i += 1
//            }
//            swap(data:&result,i:start,j:index-1)
//            return index-1
        }
        
        func quickSortStart(_ data: inout Array<Int>, _ start:Int, _ end:Int)->Any {
            if start < end {
                let pivotIndex = findPoint(result: &data, start: start, end: end)
//                let pivotIndex = findPoint2(result: &data, start: start, end: end)
                data = quickSortStart(&data, start, pivotIndex-1) as! Array<Int>
                data = quickSortStart(&data, pivotIndex+1, end) as! Array<Int>
            }
            return data
        }
        
        var dataAry:Array<Int> = data
        let result = quickSortStart(&dataAry,0,num)
        print("快速排序：",result)
        return result
        
        
    }
    
    /// 堆排序
    static func heapSort(_ data:Array<Int>)->Any {
        var dataAry:Array<Int> = data
        if dataAry.count < 2 {
            return dataAry
        }
        var arrLength = data.count
        
        func swap(data: inout Array<Int>, i:Int, j:Int) {
            let temp = data[i]
            data[i] = data[j]
            data[j] = temp
        }
        
        func heapify(_ data: inout Array<Int>, _ i:Int) {
            let left = 2*i + 1
            let right = 2*i + 2
            var largest = i
            if left < arrLength && data[left] > data[largest] {
                largest = left
            }
            if right < arrLength && data[right] > data[largest] {
                largest = right
            }
            if largest != i {
                swap(data: &data, i: i, j: largest)
                heapify(&data, largest)
            }
        }
        
        func buildHeap(_ data: inout Array<Int>) {
            for i in (0..<data.count/2).reversed() {
                heapify(&data, i)
            }
        }
        
        buildHeap(&dataAry)
        for i in (1..<dataAry.count).reversed() {
            swap(data: &dataAry, i: 0, j: i)
            arrLength -= 1
            heapify(&dataAry, 0)
        }
        
        print("堆 排 序: \(dataAry)")
        return dataAry
    }
    
    /// 计数排序
    static func countSort(_ data:Array<Int>)->Any {
        let dataAry:Array<Int> = data
        if dataAry.count < 2 {
            return dataAry
        }
        //计算最大最小值，得到临时数组的长度
        var minValue = 0
        var maxValue = 0
        for item in dataAry {
            minValue = min(minValue, item)
            maxValue = max(maxValue, item)
        }
        let tempLen = maxValue - minValue + 1
        //初始化临时数组
        var temp:Array<Int> = [Int].init(repeating: 0, count: tempLen)
        //源数组的值为key，出现次数为value存储到临时数组
        for item in dataAry {
            temp[item-minValue] += 1
        }
        //初始化结果数组
        var result:Array<Int> = [Int].init(repeating: 0, count: dataAry.count)
        var index = 0
        for i in 0..<tempLen {
            while temp[i] > 0 {
                result[index] = i + minValue
                index += 1
                temp[i] -= 1
            }
        }
        print("计数排序： \(result)")
        return result
    }
    
    /// 桶排序
    static func bucketSort(_ data:Array<Int>)->Any {
        var dataAry:Array<Int> = data
        let dataLength = dataAry.count
        
        if dataLength < 2 {
            return dataAry
        }
        //计算最大最小值，得到桶数量
        var minValue = 0
        var maxValue = 0
        for item in dataAry {
            minValue = min(minValue, item)
            maxValue = max(maxValue, item)
        }
        //计算桶的数量
        let bucketNum = (maxValue - minValue) / dataLength + 1
        var bucketArr:Array<Array<Int>> = [Array].init(repeating: [Int](), count: bucketNum)
        //将源数组元素放入各个桶中
        for item in dataAry {
            let num = (item - minValue)/dataLength
            bucketArr[num].append(item)
        }
        //各个桶中元素进行排序（快排）
        for i in 0..<bucketNum {
            let bucketResult:Array<Int> = quickSort(bucketArr[i]) as! Array<Int>
            //桶内数据排序时做了深拷贝，这里需要替换排序好的桶
            bucketArr[i] = bucketResult
        }
        //将所有桶中元素取出
        var index = 0
        for item in bucketArr {
            for i in 0..<item.count {
                dataAry[index] = item[i]
                index += 1
            }
        }
        print(" 桶 排序: \(dataAry)")
        return dataAry
    }
    
    /// 基数排序
    static func radixSort(_ data:Array<Int>)->Any {
        var dataAry:Array<Int> = data
        if dataAry.count < 2 {
            return dataAry
        }
        
        func digitsSort(_ data: inout Array<Int>, _ exp:Int)->Any {
            // 存储本次排序结果的临时数组
            var result:Array<Int> = Array.init(repeating: 0, count: data.count)
            // 用于排序的桶，由于每一位的数字只能是[0-9)，所以默认新建长度为10的数组
            var bucket:Array<Int> = Array.init(repeating: 0, count: 10)
            // 源数组每一项数据当前位数的值为key，出现次数为value存储到桶中
            for item in data {
                bucket[(item/exp)%10] += 1
            }
            // 这里修改后使得buckets[i]的值就是排序后该数据在源数组中应处的位置
            for i in 1..<bucket.count {
                bucket[i] += bucket[i-1]
            }
            for i in (0..<data.count).reversed() {
                let num = (data[i]/exp)%10
                result[bucket[num]-1] = data[i]
                bucket[num] -= 1
            }
            for i in 0..<data.count {
                data[i] = result[i]
            }
            return data
        }
        
        let maxValue:Int = { () -> Int in
            var value = dataAry[0]
            for item in dataAry {
                value = max(item, value)
            }
            return value
        }()
        // exp:排序位数，各位1，十位1*10...
        var exp = 1
        while maxValue/exp > 0 {
            dataAry = digitsSort(&dataAry, exp) as! Array<Int>
            exp *= 10
        }
        print("基数排序： \(dataAry)")
        return dataAry
    }
}