排序专题一

1、选择排序

class Solution(object):
    def sortArray(self, nums):
        l = len(nums)    
        for i in range(l-1):
            min_i = i                                     
            for j in range(i+1,l):
                if(nums[min_i]>nums[j]):         
                    min_i = j
            if i != min_i:
                nums[i],nums[min_i] = nums[min_i],nums[i]
        return nums

大循环控制当前将要排序的元素，小循环从将要排序的元素的下一个位置开始遍历，寻找比当前元素更小的元素，若找到则将其下标赋予min_i。

循环结束，若当前元素不是最小，则当前元素与nums[min_i]交换。

2、插入排序

class Solution(object):
    def sortArray(self, nums):
        l = len(nums)    
        for i in range(1,l):
            temp = nums[i]
            j = i
            while j>0 and nums[j-1]>temp:
                nums[j] = nums[j-1]
                j -= 1
            nums[j] = temp
        return nums

1、从数组的第二个元素开始遍历，首先记录它的值至temp中，记录它的下标至j中；

2、当 j大于0 且当前元素的值temp小于前一个元素的值nums[j-1]时，就将前一个元素向后移一位，循环操作；

3、退出循环后，将temp赋给nums[j]，即将i所指的元素插入到升序位置上。

3、希尔排序

class Solution(object):
    def sortArray(self, nums):
        size = len(nums)    
        gap = size//2
        while gap > 0:
            for i in range(gap,size):
                temp = nums[i]
                j = i
                while j>=gap and nums[j-gap]>temp:
                    nums[j] = nums[j-gap]
                    j -= gap
                nums[j] = temp
            gap //= 2
        return nums

1、希尔排序将数组按照一定的间隔分为若干个组，再利用插入排序进行排序，间隔一般为size/2；

2、递归运行直至间隔为1，虽然原始数组就是间隔为1的数组，但是通过分组的方法可以大大减少运行时间。

4、归并排序

def merge(left_arr, right_arr):
    arr = []
    while left_arr and right_arr:
        if left_arr[0] <= right_arr[0]:
            arr.append(left_arr.pop(0))
        else:
            arr.append(right_arr.pop(0))
    while left_arr:
        arr.append(left_arr.pop(0))
    while right_arr:
        arr.append(right_arr.pop(0))
    return arr

def mergeSort(arr):
    size = len(arr)
    if size < 2:
        return arr
    mid = len(arr) // 2
    left_arr, right_arr = arr[0: mid], arr[mid:]
    return merge(mergeSort(left_arr), mergeSort(right_arr))

归并排序将数组依次分为len（nums）个组，len（nums-1）组……直到1个组，合并组时按照两个组中第一个元素的相对大小进行出栈，当其中一组的元素个数为0时，便直接将另一组的元素按照原来的顺序全部添加到新的数组中，递归上述过程直到所有的组合并为1个数组，完成排序。

5、快速排序

import numpy as np
import sys
np.random.seed(1)
nums = np.random.randint(10,size=8)
print(nums)
def QuickSort(nums,left,right):
    if left >= right:
        return 0
    basenumber = nums[left]
    i = left
    j = right
    while i!=j:
        while i < j and nums[j] >= basenumber:
            j -= 1
        while j > i and nums[i] <= basenumber:
            i += 1
        if i < j:
            nums[i],nums[j] = nums[j],nums[i]

    nums[i],nums[left] = nums[left],nums[i]
    
    QuickSort(nums,left,i-1)
    QuickSort(nums,i+1,right)
QuickSort(nums,0,nums.size-1)
print(nums)