题解 | #排序#

排序

http://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896

https://www.cnblogs.com/onepixel/articles/7674659.html

1. 快速排序快排

时间复杂度：O（nlogn）空间复杂度：O（1）
不稳定

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr ):
        # write code here
        self.quick_sort(0, len(arr)-1, arr)
        return arr

    def quick_sort(self, start, end, arr):
        if start >= end:
            return

        left, right = start, end
        pivot = arr[(start + end)//2]

        while left <= right:
            while left <= right and arr[left] < pivot:
                left += 1
            while left <= right and arr[right] > pivot:
                right -= 1

            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1

        self.quick_sort(start, right, arr)
        self.quick_sort(left, end, arr)

2. 冒泡排序

一对一对的比较反复loop
367219 - 362179 - 321679 - 213679 - 123679

时间复杂度：O（n^2）空间复杂度：O（1）

3. 选择排序

选一个最大或最小值放在起始位，不断loop后面的找到最值，更新在后面的位置
367219 - 167239 - 127639 - 123679

时间复杂度：O（n^2）空间复杂度：O（1）

4. 插入排序

每次把当前元素跟前面排好的相比，不断地swap到应该在的地方
367219 - 236719 - 123679

时间复杂度：O（n^2）空间复杂度：O（1）

5. 归并排序

时间复杂度：O（nlogn）空间复杂度：O（1）
稳定

class Solution:
    def MySort(self , arr ):
        # write code here
        temp = [0 for _ in range(len(arr))]
        self.merge_sort(0, len(arr) - 1, arr, temp)
        return arr

    def merge_sort(self, start, end, arr, temp):
        if start >= end:
            return

        mid = (start + end) // 2

        self.merge_sort(start, mid, arr, temp)
        self.merge_sort(mid + 1, end, arr, temp)
        self.merge(start, mid, end, arr, temp)

    def merge(self, start, mid, end, arr, temp):
        left, right = start, mid + 1
        index = start

        while left <= mid and right <= end:
            if arr[left] < arr[right]:
                temp[index] = arr[left]
                left += 1
            else:
                temp[index] = arr[right]
                right += 1
            index += 1


        while left <= mid:
            temp[index] = arr[left]
            left += 1
            index += 1

        while right <= end:
            temp[index] = arr[right]
            right += 1
            index += 1

        for index in range(start, end+1):
            arr[index] = temp[index]