排序算法

十大经典排序算法

排序算法	平均时间复杂度	最好	最坏	空间复杂度	稳定性
冒泡	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快排	$O(nlog(n))$	$O(nlog(n))$	$O(n^2)$	$O(log(n))$	不稳定
归并	$O(nlog(n))$	$O(nlog(n))$	$O(nlog(n))$	$O(n)$	稳定

冒泡算法

template<typename T>
void bubbleSort(T arr[], int len){
    for(int i = 0; i < len; i++){
        for(int j=1; j < len - i; j++){
            if(arr[j] < arr[j-1]){
                swap(arr[j], arr[j-1]);
            }
        }
    }
}

def bubbleSort(arr):
    for i in range(0, len(arr)):
        for j in range(1, len(arr)-i):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr 

快速排序

void quickSort(int[] src, int begin, int end){
    if(begin < end){
        int key = src[begin]
        int i = begin;
        int j = end;
        while(i < j){
            while(i < j && src[j] > key){
                j--;
            }
            if(i < j){
                src[i] = src[j];
                i++;
            }
            while(i < j && src[i] < key){
                i++;
            }
            if(i < j){
                scr[j] = scr[i];
                j--;
            }
        }
        scr[i] = key;
        quickSort(src, begin, i - 1);
        quickSort(src, i + 1, end);
    }
}

int quick(int A[], int low, int high){
    int key = A[low];
    while(low < high){
        while(low < high && A[high] >= key){
            --high;
        } 
        A[low] = A[high];
        while(low < high && A[low] <= key){
            ++low;
        }
        A[high] = A[low];

    }
    A[low] = key;
    return low;
}

void quickSort(int A[], int low, int high){
    if(low < high){
        int key = quick(A, low, high);
        quickSort(A, low, key - 1);
        quickSort(A, key + 1, high);
    }
}

def quick(nums, low, high):
    key = nums[low]
    while low < high:
        while low < high and nums[high] >= key:
            high -= 1
        nums[high], nums[low] = nums[low], nums[high]
        while low < high and nums[low] <= key:
            low += 1
        nums[low], nums[high] = nums[high], nums[low]
    
    nums[low] = key
    return low

def quicksort(nums, low, high):
    if low < high:
        mid = quick(nums, low, high)
        quicksort(nums, low, mid - 1)
        quicksort(nums, mid + 1, high)
    
    return nums

归并排序

template<typename T>
void merge(T arr[], T res[], int start, int end){
    if(start >= end)
        return;
    
    int len = end - start;
    int mid = start + (len >> 1);
    int start1 = start;
    int end1 = mid;
    int start2 = mid + 1;
    int end2 = end;

    merge(arr, reg, start1, end1);
    merge(arr, reg, start2, end2);
    int k = start;
    while(start1 <= end1 && start2 <= end2){
        res[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    }

    while(start1 <= end1)
        reg[k++] = arr[start1++];
    
    while(start2 <= end2)
        reg[k++] = arr[start2++];
    
    for( k = start; k<=end; k++)
        arr[k] = reg[k];
}

template<typename T>
void mergeSort(T arr[], const int len){
    T reg[len];
    merge(arr, reg, 0, len -1 );
}

def merge(left, right):
    result = []
    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

def mergesort(nums):
    if len(nums) < 2:
        return nums
    mid = len(nums) // 2
    left = mergesort(nums[:mid])
    right = mergesort(nums[mid:])
    return merge(left, right)