数据结构之排序算法汇总

排序算法有十多种，按类别来分有交换排序，插入排序，选择排序。其中交换排序有冒泡排序和快速排序，其通过交换元素的前后顺序进行排序；插入排序是将数据逐次插入到有序的数据列中，达到排序的
目的，其有简单插入排序和希尔排序；
冒泡排序：遍历列表，比较相邻两个数据的大小，后者较小，则交换位置，相当于泡泡，逐次的后移。每次遍历可以将最大值移动到末尾。
快速排序：取出任意一个数据作为比较值，然后定义start和end两个指针，分别用来从数据列表的开头和末尾进行遍历。首先从末尾进行遍历，若end指针指向的数据小于比较值，则进行交换，
交换后末尾指针停止遍历；接着，start指针开始遍历，若start指针指向的数据大于比较值，则进行交换，start指针停止遍历。
希尔排序：将简单插入排序进行改进，其步长大于1，因此排序更加高效。其思想是根据步长，将数据分组，然后进行简单排序；随后减小步长，再简单排序，直到步长为1，进行简单排序。
一般在数据量大时，较高效。

class Sort():
    # 冒泡排序时间复杂度O（n!）
    def puplle_sort(self, data_list):
        length = len(data_list)
        for j in range(length - 1):
            for i in range(length - j - 1):
                if data_list[i] > data_list[i + 1]:
                    data_list[i], data_list[i + 1] = data_list[i + 1], data_list[i]
        return data_list

    # 快速排序时间复杂度nlgn : 4,1
    def quick_sort(self, data_list):
        length = len(data_list)
        if length < 2:
            return data_list
        ref_data = length // 2
        start = 0
        end = length - 1
        bool = 1
        while 1:
            if start > end:
                break
            if bool:
                if (data_list[ref_data] >= data_list[end]):
                    data_list[ref_data], data_list[end] = data_list[end], data_list[ref_data]
                    ref_data = end
                    bool = 0
                end -= 1
            else:
                if (data_list[ref_data] <= data_list[start]):
                    data_list[ref_data], data_list[start] = data_list[start], data_list[ref_data]
                    ref_data = start
                    bool = 1
                start += 1
        data_list[:ref_data] = self.quick_sort(data_list[:ref_data])
        data_list[(ref_data + 1):] = self.quick_sort(data_list[(ref_data + 1):])
        return data_list

　　# 插入排序时间复杂度O(n^2)
　　def insert_sort(self, data_list):
    　　for i in range(1, len(data_list)):
       　　 j = i
       　　 while 1:
            　　if data_list[j - 1] > data_list[j]:
                　　data_list[j - 1], data_list[j] = data_list[j], data_list[j - 1]
                　　j -= 1
            　　else:
                　　break
            　　if j < 1:
                　　break
    　　return  data_list

#希尔排序时间复杂度O(n^1.3-2) 
    def shell_insert(self,data_list):
        length=len(data_list)
        length1=length
        while 1:
            length1 = length1 // 2#步长
            if length1<1:
                break
            for k in range(length1):
                # k+n*length1<=length-1
                length2=(length-k-1)//length1+1
                for i in range(1,length2):
                    j=i
                    while 1:
                        if j<1:
                            break
                        if data_list[k+length1*(j-1)] > data_list[k+length1*j]:
                            data_list[k+length1*(j-1)], data_list[k+length1*j] = data_list[k+length1*j], data_list[k+length1*(j-1)]
                            j -= 1
                        else:
                            break
        return  data_list