数据结构篇 (4) 排序

文本主要介绍各种排序算法的核心思想和代码实现。

1.冒泡排序(bubble sort)
每个回合都从第一个元素开始和它后面的元素比较,如果比它后面的元素更大的话就交换,一直重复,直到这个元素到了它能到达的位置。每次遍历都将剩下的元素中最大的那个放到了序列的“最后”(除去了前面已经排好的那些元素)。注意检测是否已经完成了排序,如果已完成就可以退出了。时间复杂度O(n^2)
image

def short_bubble_sort(a_list):
    exchanges = True
    pass_num = len(a_list) - 1
    while pass_num > 0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                exchanges = True
                a_list[i],a_list[i+1] = a_list[i+1], a_list[i]
        pass_num = pass_num - 1


if __name__ == '__main__':
    a_list=[20, 40, 30, 90, 50, 80, 70, 60, 110, 100]
    short_bubble_sort(a_list)
    print(a_list)

2.选择排序(selection sort)
每个回合都选择出剩下的元素中最大的那个,选择的方法是首先默认第一元素是最大的,如果后面的元素比它大的话,那就更新剩下的最大的元素值,找到剩下元素中最大的之后将它放入到合适的位置就行了。和冒泡排序类似,只是找剩下的元素中最大的方式不同而已。时间复杂度O(n^2)
image

def selection_sort(a_list):
    for fill_slot in range(len(a_list) - 1, 0, -1):
        pos_of_max = 0
        for location in range(1, fill_slot + 1):
            if a_list[location] > a_list[pos_of_max]:
                pos_of_max = location
        a_list[fill_slot],a_list[pos_of_max]=a_list[pos_of_max],a_list[fill_slot]


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print(a_list)

3.插入排序(insertion sort)
每次假设前面的元素都是已经排好序了的,然后将当前位置的元素插入到原来的序列中,为了尽快地查找合适的插入位置,可以使用二分查找。时间复杂度O(n^2),别误以为二分查找可以降低它的复杂度,因为插入排序还需要移动元素的操作!
image

def insertion_sort(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        while position > 0 and a_list[position - 1] > current_value:
            a_list[position] = a_list[position - 1]
            position = position - 1
        a_list[position] = current_value


def insertion_sort_binarysearch(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        low=0
        high=index-1
        while low<=high:
            mid=(low+high)/2
            if a_list[mid]>current_value:
                high=mid-1
            else:
                low=mid+1
        while position > low:
            a_list[position] = a_list[position - 1]
            position = position -1
        a_list[position] = current_value


a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)

4.合并排序(merge sort)
典型的是二路合并排序,将原始数据集分成两部分(不一定能够均分),分别对它们进行排序,然后将排序后的子数据集进行合并,这是典型的分治法策略。时间复杂度O(nlogn)
image
image

def merge_sort(a_list):
    print("Splitting ", a_list)
    if len(a_list) > 1:
        mid = len(a_list) // 2
        left_half = a_list[:mid]
        right_half = a_list[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        i=0;j=0;k=0;
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                a_list[k] = left_half[i]
                i=i+1
            else:
                a_list[k] = right_half[j]
                j=j+1
            k=k+1
        while i < len(left_half):
            a_list[k] = left_half[i]
            i=i+1
            k=k+1
        while j < len(right_half):
            a_list[k] = right_half[j]
            j=j+1
            k=k+1
    print("Merging ", a_list)


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(a_list)
print(a_list)

算法导论2-4题利用合并排序可以在O(nlogn)的最坏情况下得到包含n个元素的数组的逆序对的数目。

[下面使用的是C++来实现的,合并排序的代码格式类似算法导论中的伪代码]

#include <iostream>
using namespace std;

int calculateInversions(int arr[], int p, int r);
int mergeInversions(int arr[], int p, int q, int r);

int main(int argc, const char * argv[])
{
    int arr[] = {2,3,8,6,1};
    int count = calculateInversions(arr, 0, 4);
    cout << "count inversions : " << count << endl;
    return 0;
}

int calculateInversions(int arr[], int p, int r) {
    int count=0;
    if(p < r) {
        int q = (p + r) / 2;
            count += calculateInversions(arr, p, q);
            count += calculateInversions(arr, q+1, r);
            count += mergeInversions(arr, p, q, r);  
    }
    return count;
}

int mergeInversions(int arr[], int p, int q, int r){
    int count=0;
    int n1=q-p+1, n2=r-q;
    int left[n1+1], right[n2+1];
    for (int i=0; i<n1; i++) {
        left[i]=arr[p+i];
    }
    for (int j=0; j<n2; j++) {
        right[j]=arr[q+1+j];
    }
    left[n1]=INT32_MAX;
    right[n2]=INT32_MAX;
    int i=0, j=0;
    for (int k=p; k<=r; k++) {
        if (left[i]<=right[j]) {
            arr[k]=left[i];
            i++;
        }else{
            arr[k]=right[j];
            count += n1-i;
            j++;
        }
    }
    return count;
}
top Created with Sketch.