排序总结 (1)

首先我们随机生成无序序列

import numpy as np
ran=np.random.randint(low=0, high=100, size=20)

快速排序

快速排序的总体思路：
给定一个长的没有排序的杂乱序列

没有排序的序列
时间复杂度：平均$O(\log(N))$，最坏情况$O\left( N^{2}\right)$
步骤

1. 随机选取一个pivot指针
2. 将pivot所在的位置与最高索引所在的位置的元素对掉
3. 设定一个元素i=最低索引
4. 从列表到最低索引low遍历到最高索引high(j)，将j号元素与pivot所在的位置high相比较大小，如果j号元素是要小于pivot的话，那么就要把j号元素和i号元素对掉（注意这个位置对掉，可是索引是不会跟着走的），同时i自己加1（这个时候的i位置其实是之前对掉后的j号元素）
5. 就这样不断遍历完列表内的所有元素，直到比pivot小的元素都被挪到了左边，并最终可以得到比pivot小的元素的最大序号+1（也就是有多少个比pivot小的元素，如果有10个，那序号就是10+1），把这个序号的元素和pivot对掉，那么得到的序列就是比pivot小的在左边，比pivot大的在右边。

我们试一下写伪代码

def quick_sort(array, low, high):
    #首先要分区，分区结束之后是得到pivot的索引，以及经过一次分区的一个array
    pivotindex=partition(array, low, high)
    quick_sort(array, low, pivotindex-1)
    quick_sort(array, pivotindex+1, high)

partition(array, low, high):
    i=low
    #初始化索引为中间值
    pivot_index=(low+high)/2
    swap(pivot_index, high)
    for j from low to high:
        if array[j]<=high:
            swap(i, j)
            i++
    swap(i, high)
    return i
end

具体代码实现

class  Solutions():
    def partition(array, low, high):
        pivot_index=(low+high)//2
        i=low
        swap(array, pivot_index, high)
        for j in range(low, high):
            if array[j]<=array[high]:
                swap(array, j, i)
                i=i+1
        swap(array, i, high)
        return i
    def quick_sort(array, low, high):
        if low>=high:
            return
        pivot_index=partition(array, low, high)
        quick_sort(array, low, pivot_index-1)
        quick_sort(array, pivot_index+1, high)
    def swap(array, i ,j)
        tmp=array[i]
        array[i]=array[j]
        array[j]=tmp
        return  

快速排序输出结果

冒泡排序

总体思路
遍历列表中的元素，每个元素都与下一个相邻元素相比较大小，如果当前元素大于下一个元素，那么就要对掉位置，所以大的元素就像冒泡一样不断冒到最右边。
时间复杂度：
要遍历列表的每个元素，对每个元素又要遍历所有的元素进行比较，最坏和平均的时间复杂度都是$O(N^{2})$。
写一下伪代码

bubble_sort(array, 0, high)
    for i from 0 to length(array)-1
        for j from 0 to length-i-1
         if array[j]>array[j+1]
             swap(j, j+1)
    end

代码如下

def swap(array, i, j):
    tmp=array[i]
    array[i]=array[j]
    array[j]=tmp
    return
def bubble_sort(array):
    for i in range(0, len(array)-1):
        for j in range(0, len(array)-i-1):
            if array[j]>array[j+1]:
                swap(array, j, j+1)
    return
bubble_sort(ran)

冒泡排序输出结果

在这里要注意冒泡排序遍历范围是从0到length(list)-1，最后一个没有比较的对象了。

选择排序

选择排序的总体思路：
遍历所有元素，当前元素所在位置i的左边是排好序的，右边是没有排序的，这一次遍历就是要从右边当中找到一个最小的元素，然后把这个元素与所在位置为i的元素位置互换。可以理解为不断地从右边没有排序的序列当中抽取出最小的值，然后跟当前元素i互换位置，这样左边依次是最小元素、次最小元素……这样的排列
时间复杂度：$O(N^{2})$
伪代码

for i from 0 to length(array)-1
    i=index
    for j from i to length(array)-1
        if array[j]<array[index]
            index=j
    if index not i
        swap(array, i, index)
end

代码如下

def selection_sort(array):
    for i in range(len(array)-1):
        index=i
        for j in range(i,len(array)-1):
            if array[j]<array[index]:
                index=j
        if index!=i:
            swap(array, i, index)
    return

输出结果

选择排序输出结果
今天总结了三种算法的实现，后续继续更新排序算法的详细介绍。关于几种排序算法的动画可以参考这里。