基础算法（排序）

2018-08-30 本文已影响0人影醉阏轩窗

只记录了一半，实习又开始了~~接下来工作写论文+实习！！

冒泡排序

原理比较简单，直接看图撸代码就懂！

冒泡排序

希尔排序

想写代码直接写，不想写代码直接复制调试就懂原理了。

希尔排序

void ShellSort(int* list,unsigned int n)
{
    int step = n / 2;
    while (step>0)
    {
        for (size_t i = step; i < n; i++)
        {
            int x = list[i];
            int j = i - step;
            while (j>=0&&x<list[j])
            {
                list[j + step] = list[j];
                j = j - step;
            }
            list[j + step] = x;
        }
        step /= 2;
    }
}

堆排序

插入排序

比较简单

插入排序

void InsertSort(int array[],unsigned int n)
{
    int temp;
    for (size_t i = 1; i < n; i++)
    {
        temp = array[i];
        for (int k = i; k > 0 && temp < array[k-1]; k--)
        {
            array[k] = array[k-1];
            array[k-1] = temp;
        }
    }
}

快速排序

原数组：{3,7,2,9,1,4,6,8,10,5}

期望结果：{1，2，3，4，5，6，7，8，9，10}

快速排序

void QuickSort(int* a,int low,int high)
{
    if (low >= high) return;
    int first = low;
    int last = high;
    int key = a[first];//记录关键数
    while (first < last)
    {//---核心代码，分治思想
        while (first < last&&a[last] >= key)
        {
            --last;
        }
        a[first] = a[last];
        while (first < last&&a[first] <= key)
        {
            ++first;
        }
        a[last] = a[first];
    }

    a[first] = key;
    QuickSort(a, low, first - 1);
    QuickSort(a, first + 1, high);
}

选择排序

原数组：{3,7,2,9,1,4,6,8,10,5}

和冒泡排序的原理差不多~~

选择排序

归并排序

原数组：{3,7,2,9,1,4,6,8,10,5}

我个人认为快速理解此算法的核心为：

原理（分治策略，几分钟就懂了）

分开（建立两个空间，把数组分开）

合并（也就是排序，自己拿个笔两个有序数组怎么合并排序？）

分治策略

注意这里的排序有可能短时间看不懂，自己用笔画一下就好了

【2,6,8】和【1,3,4】进行整合排序，

A. 首先要明白一点，左右都是有序的排列

B. 有序排列那么只需要比较最小（最大）的数据就可以了，其它的肯定是比他大（小）

C. 存储在新的数组里面OK

排序策略

归并排序

/归并排序
//将两个有序数组排序
void Merge(int *list, int start, int mid, int end)
{
    const int len1 = mid - start + 1;
    const int len2 = end - mid;
    const int len = end - start + 1;
    int i, j, k;

    int * front = (int *)malloc(sizeof(int)*len1);
    int * back = (int *)malloc(sizeof(int)*len2);

    for (i = 0; i<len1; i++)
        front[i] = list[start + i];
    for (j = 0; j<len2; j++)
        back[j] = list[mid + j + 1];
    // for循环里面的判断有点饶人
    //（i<len1||j<len2）和‘end+1’，是为了给【3,7】和【2】合并使用
    // 其它的都是正常的循环判断
    for (i = 0, j = 0, k = start; (i<len1||j<len2)&&k<end+1; k++)
    {   //i,j是新申请的堆空间的下标
        //k是list的下标
        if (front[i]<back[j]||j>=len2)
        {
            list[k] = front[i];
            i++;
        }
        else
        {
            list[k] = back[j];
            j++;
        }
    }
}

void MSort(int *list, int start, int end)
{
    if (start<end)
    {
        int mid = (start + end) / 2;
        MSort(list, start, mid);
        MSort(list, mid + 1, end);
        Merge(list, start, mid, end);
    }

}