十大经典排序算法

算法说明

十大排序算法分别是：

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

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
    }
}