python c 排序算法实现 插入，合并排序

插入排序

插入排序算法比较简单的排序了。基本思想就是存在一有序数列，然后将数插入到有序数列中去。跟扑克码牌的过程基本一样。

C：

#include <stdio.h>
void display(int nums[], int len);
void insert_sort(int nums[], int len);

int main(int argc, char* argv)
{
    int nums[4] = {2,53,12,3};
    insert_sort(nums, 4);
    display(nums, 4);
    return 0;
}

void display(int nums[], int len)
{
    int i = 0;
    for (i=0; i<len; i++)
    {
        printf("%d ", nums[i]);
    }
}

void insert_sort(int nums[], int len)
{
    int i = 0;
    int j = 0;
    int key = 0;

    for (i=1; i<len; i++)
    {
        key = nums[i];
        j = i - 1;
        while (j >= 0 && key < nums[j])
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}

python:

#!/usr/bin/python
def insert_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j = j - 1
        nums[j + 1] = key
    return nums

if __name__ == '__main__':
    nums = [2, 4, 1,33,11]
    print nums
    print insert_sort(nums)

合并排序

合并排序也称归并排序。是分治法的典型应用。分治思想是将每个问题分解成个个小问题。将每个小问题解决。然后合并。

具体的合并排序就是，将一组无序数按n/2递归分解成只有一个元素的子项。一个元素就是已经排好序的了。然后将这些有序的子元素进行合并。

C：

#include <stdio.h>
#include <malloc.h>

#define MAX (1 << 30)
void display(int nums[], int len);
void merge(int nums[], int first, int middle, int last);
void merge_sort(int nums[], int first, int last);

int main(int argc, char* argv[])
{
    int nums[] = {21,33,4,24,23,54,2};
    merge_sort(nums, 0, 6);
    display(nums, 7);
    return 0;
}

void merge_sort(int nums[], int first, int last)
{
    int middle = 0;
    if (first < last)
    {
        middle = (first + last) / 2;
        merge_sort(nums, first, middle);
        merge_sort(nums, middle + 1, last);
        merge(nums, first, middle, last);
    }
}

void merge(int nums[], int first, int middle, int last)
{
    int n1 = middle - first + 1;
    int n2 = last - middle;
    int *lnums = (int*)malloc(sizeof(nums[0]) * (n1+1));
    int *rnums = (int*)malloc(sizeof(nums[0]) * (n2+1));
    int i = 0;
    int p,q;

    //左数组赋值
    for (i=0; i<n1; i++)
    {
        lnums[i] = nums[first+i];
    }
    lnums[i] = MAX;

    //右数组赋值
    for (i=0; i<n2; i++)
    {
        rnums[i] = nums[i+middle+1];
    }
    rnums[i] = MAX;

    //合并
    p = q = 0;
    for (i=first; i<=last; i++)
    {
        if (lnums[p] < rnums[q])
        {
            nums[i] = lnums[p];
            p++;
        }
        else
        {
            nums[i] = rnums[q];
            q++;
        }
    }
    free(lnums);
    free(rnums);
}

千万注意合并排序中的边界问题，很容易出错。在这种解法中合并步骤中的循环是从first到last+1所以这是<=last，因为main函数中merge_sort函数中传递的是下标，不是元素个数。

python:

#!/usr/bin/python
import sys

def merge(nums, first, middle, last):

    n1 = middle - first + 1
    n2 = last - middle
    lnums = nums[first:middle+1]
    rnums = nums[middle+1:last+1]
    lnums.append(sys.maxint)
    rnums.append(sys.maxint)
    p = q = 0
    for i in range(first, last+1):
        if lnums[p] < rnums[q]:
            nums[i] = lnums[p]
            p += 1
        else:
            nums[i] = rnums[q]
            q += 1
    print nums

def merge_sort(nums, first, last):
    middle = 0
    if first < last:
        middle = (first + last) / 2
        merge_sort(nums, first, middle)
        merge_sort(nums, middle+1, last)
        merge(nums, first, middle, last)

if __name__ == '__main__':
    nums = [21, 33, 4, 24, 23, 54, 2]
    print nums
    print merge_sort(nums, 0, 6)
    print nums

python 中代码应注意在merge()函数中的切片边界。一定注意是左闭右开并且是了0为开始。