c语言数据结构 排序（一）

好久之前的博客有提到说我想写一篇关于基本排序类型的总和，现在终于有机会可以实现了！

一.插入排序

思路:好比是打扑克牌，摸得第一张是有序的。再摸一张牌，就排这两张牌的序，使得手里现有两张牌是有序的，依次类推，每当摸得一张牌，就要使得整个数组是有顺序的。

代码实现如下图所示

时间复杂度为O(N^2) 可以良好地适应于局部有序

2.希尔排序

思路：1.预排序，目的使得数组接近有序 2.直接插入排序

代码实现如下：

//希尔排序
void ShellSort(int* a, int n)
{
    //1.预排序
    //思路：间隔为gap的数据为一组插入排序
    //目的：使得数组尽量有序
    
    int gap=3;
    //gap越大，大数据越快到后面，小数据越快到前面
    //gap越小，进行预排序的次数越多，排的数组就有序
    //gap>1--预排序 gap==1直接排序 
    //不断进行预排序会使得数据相当有序
    while (gap > 1)
    {

        gap = gap / 2;//无论奇数还是偶数都可使得结果为1 log2N
        //gap=gap/3+1 //无论奇数还是偶数都可以使得结果为1 log3N 
        // N越大 第一种方式进行的预排序的次数就越多
        //两层循环---将一组数据分为不同的数组 第一层循环控制每组数组的起始点 第二层循环保证遍历每个数组的每个数据
        //
//第一层循环
        for (int j = 0; j < gap; j++)
        {
            //第二层循环
            for (int i = j; i < n - gap; i += gap)
            {
                int end = i;
                //单趟排序
                int tmp = a[end + gap];
                //2.将数组的最后一位数与前者进行比较，使得整个数组是呈升序状态的
                while (end >= 0)
                {
                    //如果大则往后挪动一位
                    if (a[end] > tmp)
                    {
                        a[end + gap] = a[end];

                        end -= gap;
                    }
                    //如果相等或者小于则保持现有位置不变
                    else
                        break;
                }
                a[end + gap] = tmp;
            }
        }

    }

}

gap=gap/3+1的时间复杂度是要比gap=gap/2的时间复杂度小一些的。

希尔排序的时间复杂度不好算，平均时间复杂度为O(N^1.3)。数据量大时，略逊于O(N*logN)的算法

3.选择排序

思路：遍历一遍数组，选出最大放在数组最后面，选出最小放在数组最前面，去除最大和最小再次对新数组进行遍历，依次类推。

最好最坏的时间复杂度均为O(N^2)

void Swap(int* a1, int* a2)
{
    int tmp = *(a1);
    *(a1) = *(a2);
    *(a2) = tmp;
}
//选择排序
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int maxi = begin, mini = begin;
        for (int i = begin + 1; i <= end; i++)
        {
            if (a[i] > a[maxi])
                maxi = i;
            if (a[i] < a[mini])
                mini = i;
        }
        Swap(&a[begin], &a[mini]);
        if (maxi == begin)
            maxi = mini;
        Swap(&a[end], &a[maxi]);
        begin++;
        end--;
    }
}

4.交换排序

a.冒泡排序

// 冒泡排序
void BubbleSort(int* a, int n)
{
    //第一层循环表示要进行的轮数
    for (int j = 0; j < n; j++)
    {
        int exchange = 0;
        //单趟逻辑
//第二层循环表示每轮要进行比较的次数
//且i控制每轮循环进行的最后一个元素的下标
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }

}

时间复杂度为O(N^2) 可以良好地适应于整体有序

b.快速排序第一种

思路：设置一个关键标准对比的值key，一般选择数组左边第一个或者是数组右边第一个。设置left和right，在key是数组左边第一个的情况下，right寻找比key小的数先行，left寻找比key大的数后行，将比key小的数和比key大的数交换，再去寻找。直到left和right相遇时，将key与相遇点的值交换。此时key所处位置，即为数组有序时key的正确位置。且数组中key前的数均小于key，key后的数字均大于key。key分裂出的两个子区间，再重复进行以上过程，便可得到一个相对有序的数组。

// 快速排序递归实现
// 快速排序hoare版本
// left找比key大的数，right找比key小的数，使得数组最后呈现key左面的数小于key，key右面的数字大于key
int PartSort1(int* a, int left, int right)
{
    //key定义为数组左边的第一个元素
    int keyi = left;
    while (left < right)
    {
        //right找小数
        while (left < right && a[right] >= a[keyi])
        {
            right--;
        }
        //left找大数
        while (left < right && a[left] <= a[keyi])
        {
            left++;
        }
        if(left          Swap(&a[left], &a[right]);
        
    }
    int meeti = left;
    Swap(&a[meeti], &a[keyi]);
    return meeti;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
    int keyi = PartSort1(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

最好时间复杂度O(N*logN)

最坏时间复杂度O(N^2)