
//插入排序
void Insert_Sort(DataType a[], int n)
{
    DataType temp;
    for (int i = 0; i < n - 1; i++)   //0 到 i 的数据已排序好
    {
        temp = a[i + 1];
        int j = i;
        while (j >= 0 && a[j] > temp) //如果是小于号则递减排序，如果是大于号则递增排序
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

二、希尔排序

1）算法思想

希尔排序算是插入排序的进阶版本，先把待排序的元素分为若干个小组，然后对每个小组进行插入排序。

这里的“增量（span）”代表将相邻span的元素分为一组，span的取值一般取n/2。

2）代码


//希尔排序
void Shell_Sort(DataType a[], int n)
{
    int span = n / 2;
    DataType temp;
    while (span > 0)
    {
        for (int i = 0; i < span; i ++)  //将数组分为span个小组
        {
            //对各组进行插入排序
            for (int k = i; k < n - span; k += span)
            {
                temp = a[k + span];
                int j = k;
                while (j >= 0 && a[j] > temp)
                {
                    a[j + span] = a[j];
                    j -= span;
                }
                a[j + span] = temp;
            }
        }
        span /= 2;
    }
}

三、选择排序

1）算法思想

每次从待排序的集合中选择最小（或最大）的元素放到集合的最前面，元素集合不断缩小，当待排序集合为空时代表排序结束。

2）代码


//选择排序
void Select_Sort(DataType a[], int n)
{
    DataType temp;
    for (int i = 0; i < n; i++)
    {
        DataType min = a[i];
        int k = i;
        for (int j = i; j < n; j++)
        {
            if (a[j] < min)
            {
                min = a[j];
                k = j;
            }
        }
        temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
}

四、堆排序

1）什么是最大堆

1、完全二叉树结构；

2、双亲节点的值都比其孩子节点大。

2）如何创建最大堆

对于一个线性表，很容易可以将其转换为完全二叉树，因为线性表元素的下标是一一对应着完全二叉树的节点。我们先来记住两个重要的对应：

（n-2）/ 2 ：表示最后一个非叶子节点；
2 * i + 1 ：表示第i个节点的左孩子；

将数组调整为大根堆的过程：

对应代码如下：


//其中n为数组a中的元素个数，h为要调整的元素的下标
static void CreatHeap(DataType a[], int n, int h)
{
    int flag = 0,i = h;
    DataType temp = a[i];
    int j = 2 * i + 1;   //先让j指向h左孩子节点的下标
 
    while (j < n && flag != 1)
    {
        //寻找左右孩子节点中的较大者，j为其下标
        if (j < n - 1 && a[j] < a[j + 1]) j++;    //第一个判断条件为该节点是否有右孩子，第二个判断条件为右孩子是否比左孩子大，若是，则j代表右节点的下标
        if (temp > a[j]) flag = 1;
        else {
            a[i] = a[j];          //将j位置的值上移，并且j更新为其左孩子节点的值
            i = j;
            j = 2 * i + 1;     
        }
    }
    a[i] = temp;
}
 
//创建大根堆
static void InitCreatHeap(DataType a[], int n)
{
    for (int i = (n - 2) / 2; i >= 0; i--)            //(n-2)/2表示左后一个非叶子节点的下标
        CreatHeap(a, n, i);
}

3）算法思想

通过第二部分的操作，我们已经成功地把数组转换为了大根堆，接下来只需要不断将根节点元素与数组末尾元素进行交换，再更新大根堆即可。

为什么不从最后面的叶子节点开始拿？因为我们无法保证最后一个元素一定是最小的！

例如：（a）将88和5进行交换，随后为保持为大根堆，5与76交换，再与50交换，得到（b）。

4）代码


void Heap_Sort(DataType a[], int n)
{
    DataType temp;
    InitCreatHeap(a, n);    //先初始化整个数组为大根堆
    for (int i = n - 1; i > 0; i--)    //不断将根节点元素放与数组末尾元素进行交换
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        CreatHeap(a, i, 0);
    }
}

五、冒泡排序

1）算法思想

冒泡排序是从第一个元素开始，将相邻的元素两个两个进行比较，每趟比较都将集合中最大（或最小）的元素放到了集合末尾。

2）代码


//冒泡排序
void Bubble_Sort(DataType a[], int n)
{
    DataType temp;
    int flag = 1;            //判断是否提前排序完成
    for (int i = n; i > 0 && flag; i--)
    {
        flag = 0;
        for (int j = 0; j < i-1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;                //仍然有元素进行交换，排序未完成
            }
        }
    }
}

六、快速排序

1）算法思想

快速排序定义了一个数组的下界low和上界high，然后通过两端的指针不断与low处的元素进行比较，将比low处的元素小的元素放到左边，将所有比他大的元素放到右边，这样一来，该元素的左边的元素都比他小，右边的元素都比他大，然后递归对左边和右边的集合进行快速排序即可。

2）代码


//快速排序
static void QuickSort(DataType a[], int low,int high)
{
    int i = low, j = high;
    DataType temp = a[low];
 
    while (i < j) {
        while (i < j && temp <= a[j])j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
 
        while (i < j && temp >= a[i])i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
    }
 
    a[i] = temp;
    if(i>low) QuickSort(a, low, i - 1);
    if(j<high) QuickSort(a, j + 1, high);
}

诶！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/正经夜光杯/article/detail/844379