【练习】常用排序以及C++/python实现

突然想要整理一下常用的排序算法，用python和C++都来写一写^_^。无论是python还是C++结构都差不多，没考虑什么优化方法。

【冒泡排序】

每次比较相邻的两个元素，若是前者比后者大，则交换两个的位置。对数组的每一对相邻两个元素进行比较，进行n-1次比较(n为数组长度)后，最后一个元素一定是最大的数。重复以上步骤，直至没有任何一对数字需要比较(每次都不用再比较前一次步骤中的最后一个数了)
例如对序列6、2、1、8、2、5、0、3、4进行排列:

python实现：

##冒泡排序
def bubble_sort(array):
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j]>array[j+1]:
                array[j],array[j+1]=array[j+1],array[j]
    return array
array1=[6,2,1,8,2,5,0,3,4]
print(bubble_sort(array1))

C++实现：

//冒泡排序
void Solution::Bubble_Sort(int array[], int length)
{
    int i, j;
    for (j = 0; j < length - 1; j++)
    {
        for (i = 0; i < length - 1 - j; i++)
        {
            if (array[i] > array[i + 1])
            {
                array[i] = array[i] ^ array[i + 1];
                array[i + 1] = array[i] ^ array[i + 1];
                array[i] = array[i] ^ array[i + 1];
            }
        }
    }
}

【直接选择排序】

将数组中第一个数字的位置用min记录，表示最小值所在位置，即将第一个数字视为当前最小值。将后面数字与最小值进行比较，若出现数字小于最小值，则更新min为这个数字所在位置，即将这个数字视为当前最小值。遍历完所有数字后，将当前最小值和第一个数字进行交换，则第一个数字是数组中最小的。以此类推，将数组中第二个数字的位置用min记录，后面过程与前面过程相同。
例如对序列6、2、1、8、2、5、0、3、4进行排列:

python实现：

##直接选择排序
def direct_select_sort(array):
    for i in range(len(array)):
        min = i
        for j in range(i+1, len(array)):
            if array[j] < array[min]:
                min = j
        array[i], array[min] = array[min], array[i]
    return array
array1=[6,2,1,8,2,5,0,3,4]
print(direct_select_sort(array1))

C++实现：

//直接选择排序
void Solution::DirectInsert_Sort(int array[], int length)
{
    int i, j, min;
    for (i = 1; i<length; i++)
    {
        min = array[i];
        j = i - 1;
        while (j >= 0 && array[j]>min)
        {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = min;
    }
}

【直接插入排序】

我们通常将第一个元素当做已经被排序的元素，取下一个元素作为待插入已排序列中的元素，记作key。在已经排列的元素序列中从后往前与key进行比较，用j来记录当前位置，若当前位置元素比key大，则j-1，向前一位再与key进行比较，直到当前位置元素小于key，或者到达这个序列的顶端(当j=0时，表示走到这个已排序列的第一个元素)。将key插入到新的位置当中。
例如对序列6、2、1、8、2、5、0、3、4进行排列:

python实现：

##直接插入排序
def insert_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array
array1=[6,2,1,8,2,5,0,3,4]
print(insert_sort(array1))    

C++实现:

//直接插入排序
void Solution::DirectInsert_Sort(int array[], int length)
{
    int i, j, key;
    for (i = 1; i<length; i++)
    {
        key = array[i];
        j = i - 1;
        while (j >= 0 && array[j]>key)
        {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = key;
    }
}

【快速排序】

每一趟排序都会选择一个基准数，标记为key，一般为了方便选择第一个数作为基准数，当然也可以随机选取。然后我们设定两个哨兵i和j，分别从待排序序列的左边和右边同时向对面前进。左边哨兵i找到一个比key大(或相等)的数就停下来，右边哨兵j找到一个比key小(或相等)的数就停下来，交换这两个数。然后哨兵i继续向右走，哨兵j继续向左走，直到i≥$\ge$j，我们将key与i所在位置的元素交换。这样我们会发现key的左边都是小于等于它的数字，而右边都是大于等于它的数字。然后递归地对左右两边的子序列按照上面的步骤进行排序，直至拆分不出新的子序列为止。
例如对序列6、2、1、8、2、5、0、3、4进行排列:

python实现:

##快速排序
def quick_sort(array, left, right):
    if left >= right:
        return array
    key = array[left]
    i = left
    j = right
    while i < j:
        while i < j and array[j] >= key:
            j -= 1
        array[i] = array[j]
        while i < j and array[i] <= key:
            i += 1
        array[j] = array[i]
    array[j] = key
    quick_sort(array, left, i - 1)
    quick_sort(array, i + 1, right)
    return array   
array1=[6,2,1,8,2,5,0,3,4]
print(quick_sort(array1))     

C++实现：

//快速排序
void Solution::Quicksort(int array[], int left, int right, int length)
{
    int i, j, key;
    if (left > right)
        return;
    key = array[left];
    i = left;
    j = right;
    while (i < j)
    {

        while (i < j && array[j] >= key)
        {
            j--;
        }
        while (i < j && array[i] <= key)
        {
            i++;
        }
        if (i < j)
        {
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }
    array[left] = array[i];
    array[i] = key;
    Quicksort(array, left, i - 1, length);
    Quicksort(array, i + 1, right, length);
}

【归并排序】

归并排序采用了典型的分治策略，将待排序列拆分成一个一个的子序列，再将这些子序列合并成有序序列。
例如对序列6、2、1、8、2、5、0、3、4进行排列:

python实现：

##归并排序
def MergeSort(array):
    if len(array) <= 1:
        return array
    num = int( len(array) / 2 )
    ##递归的拆分左子序列和右子序列
    left = MergeSort(array[:num])
    right = MergeSort(array[num:])
    return Merge(left,right)
##归并    
def Merge(left,right):
    l, r = 0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result
array1=[6,2,1,8,2,5,0,3,4]
print(MergeSort(array1))

C++实现：

//归并排序
void Solution::Mergesort(int *array, int start, int end, int *result)
{
    if (start < end)
    {
        int mid = (start + end) / 2;
        Mergesort(array, start, mid, result);                    
        Mergesort(array, mid + 1, end, result);                  
        Merge(array, start, mid, end, result);                    
    }
}

void Solution::Merge(int *array, int start, int mid, int end, int *result)
{
    int l, r, k;
    l = start;
    r = mid + 1;                        
    k = 0;
    while (l <= mid && r <= end)//mid即为左子序列长度，end即为右子序列长度        
    {
        if (array[l] <= array[r])        
            result[k++] = array[l++];    
        else
            result[k++] = array[r++];    
    }
    while (l <= mid)                    
        result[k++] = array[l++];        
    while (r <= end)                    
        result[k++] = array[r++];        

    for (l = 0; l < k; l++)             
        array[start + l] = result[l];    
}

复杂度