C语言排序

什么是排序？

就是将无序的变成有序的

1.冒泡排序

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。每一趟排序后的效果都是讲没有沉下去的元素给沉下去。

主要思路：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2.对每一个相邻元素做同样的工作，从开始第一对到结尾的每一对。在这一 点，最后的元素应该会是最大的数。
3.针对多有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较。

demo

#include <stdio.h>

//冒泡排序
void BubbleSort(int arry[],int len)
{
        int i;
        int j;
        int temp;
        for(i=0;i<len-1;i++)//比较次数
        {
                for(j=0;j<len-1-i;j++)//比较过程
                {
                        if(arry[j]>arry[j+1]) //比较大小
                        {
                                temp=arry[j];
                                arry[j]=arry[j+1];
                                arry[j+1]=temp;

                        }
                }

        }

}
//输出
void print(int arry[],int len)
{
        int i;
        for(i=0;i<len;i++)
        {
                printf("%d ",arry[i]);
        }
}
int main()
{

        int arry[10]={9,3,56,44,77,88,54,79,52,111};

        BubbleSort(arry,10);
        print(arry,10);
        printf("\n");

        return 0;
}

2.选择排序

基本思想

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

主要思路

每一次从无序组的数据元素中选出最小的一个元素，存放在无序组的起始位置，无需组的元素减少，有序组的元素增加，直到全部待排序的数据元素排完。

demo

#include <stdio.h>

//选择排序
void selectSort(int arry[], int len)
{       int i;
        int j;
        for ( i = 0; i < len-1; i++)
        {
                int min = i;//假设第一个元素是最小的
                for (j = i + 1; j < len; j++)
                {
                        if (arry[j] < arry[min])
                        {
                                min = j;//保存最小元素的下标
                        }
                }
                //交换
                int temp = arry[min];
                arry[min] = arry[i];
                arry[i] = temp;
        }
}
//输出
void print(int arry[], int len)
{
        for (int i = 0; i < len; i++)
        {
                printf("%d ", arry[i]);
        }
}
int main()
{
        int arry[10]={15,36,26,27,24,46,44,29,52,48};
        selectSort(arry,10);
        print(arry,10);


        printf("\n");
        return 0;
}

3.插入排序

基本思想

将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列，将无序数列中的元素逐次插入到有序数列中，从而获得最终的有序数列。

主要思路

插入排序是最简单常用的方法，将数组分为两部分，排好序的数列，以及未排序的数列，将未排序的数列中的元素 与排好序的数列进行比较，然后将该元素插入到已排序列的合适位置中。

demo

#include <stdio.h>

//插入排序
void insertSort(int arry[], int len)
{
        int i;
        int temp;//保存要插入的元素
        int j;//从当前要要比较插入的元素的前面一个开始
        for ( i = 1; i < len; i++)//第一个元素视为有序,把后面的元素一个一个的插入到前面
        {
                temp = arry[i];
                j = i - 1;
                while (j >= 0&&arry[j]>temp)
                {
                        arry[j + 1] = arry[j];//前面的元素往后面移动
                        j--;
                }
                arry[j + 1] = temp;//把要插入的元素,插入进对应的位置
        }
}
//输出
void print(int arry[], int len)
{
        for (int i = 0; i < len; i++)
        {
                printf("%d ", arry[i]);
        }
}
int main()
{
        int arry[10]={3,44,38,5,47,15,36,26,27,2};
        insertSort(arry,10);
        print(arry,10);


        printf("\n");
        return 0;
}

4.快速排序

基本思想

快速排序算法的基本思想为分治思想。
先从数列中取出一个数作轴值（基准数）pivot；
根据基准数将数列进行分区，小于基准数的放左边，大于基准数的放右边；
重复分区操作，知道各区间只有一个数为止。

主要思路

快速排序是找出一个元素（理论上可以随便找一个）作为基准，然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n - 1 个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，及如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

demo

#include <stdio.h>

//快速排序
void quickSort(int arry[], int low, int high)
{
        if (low > high)
        {
                return;
        }
        int i = low, j = high, temp = arry[i];//获取左右和基准数
        while (i < j)
        {
                while (temp < arry[j] && i < j)
                {
                        j--;
                }
                if (i < j)
                  {
                        arry[i++] = arry[j];
                  }
                while (temp>arry[i] && i < j)
                    {

                        i++;
                     }
                if (i < j)
                    {
                        arry[j--] = arry[i];
                    }
        }
        arry[i] = temp;

        quickSort(arry, low, i - 1);//左边
        quickSort(arry, i + 1, high);//右边
}
//输出
void print(int arry[], int len)
{
        for (int i = 0; i < len; i++)
        {
                printf("%d ", arry[i]);
        }
}
int main()
{

        int arry[15]={7,44,38,99,47,15,36,26,27,2,46,43,19,50,48};
        quickSort(arry,0,14);
        print(arry,15);

        printf("\n");
        return 0;
}