实用且有效的排序算法

骑猪看日落 2022-10-07 13:51 161阅读 0赞

**排序概念**

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。

*  排序是数据元素从无序到有序的过程
 *  排序具有稳定性，是选择排序算法的因素之一
 *  比较和交换是排序的基本操作
 *  排序的时间性能是区分排序算法好坏的主要因素。

排序中的关键环节：

*  比较：任意两个数据元素通过比较操作确定先后次序
 *  交换：数据元素之间需要交换才能得到预期结果
 *  内排序：整个排序过程不需要访问外存便能完成
 *  外排序：待排序的数据元素数量较多，整个序列的排序过程不可能在内存中完成
 *  辅助存储空间：为完成排序操作需要的额外的存储空间，必要时可以“空间换时间”。  
    **选择排序算法**

思想步骤：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

设数组为a\[0…n-1\]。

*  初始时，数组为无序区为a\[0..n-1\]。令i=0
 *  在无序区a\[i…n-1\]中选取一个最小的元素，将其与a\[i\]交换。交换之后a\[0…i\]就形成了一个有序区。
 *  i++并重复第二步直到i=n-1。

算法实现：

//升序排列void selectsort(int * array,int len){
       int i,j;int minindex=0;for(i=0;i<len-1;i++){
       minindex=i;   for(j=i+1;j<len-1;j++)     {
               if(array[minindex]>array[j])        {
                    minindex=j;        }     }     //交换元素     if(minindex!=i)     {
               int temp=array[i];        array[i]=array[minindex];        array[minindex]=temp;     } }}

**冒泡排序算法**

思想步骤：

*  比较相邻的元素。如果第一个元素比第二个元素大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
 *  针对所有的元素重复以上的步骤。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

void bubblesort(int * array,int len){
          int i,j;   int temp;   for(i=0;i<len-1;i++)     {
            for(j=0;j<len-1-i;j++)         {
                    if(array[j+1]<array[j])             {
                           temp=array[j];                    array[j]=array[j+1]；                    array[j+1]=temp;             }         }     }}

**冒泡优化算法**

void BubbleSort(int arr[], int len){
         int i = 0;  int tmp = 0;  for (i = 0; i < len - 1; i++)  {
           int j = 0;    int flag = 0;    for (j = 0; j < len - 1 - i; j++)    {
             if (arr[j]>arr[j + 1])      {
               tmp = arr[j];        arr[j] = arr[j + 1];        arr[j + 1] = tmp;        flag = 1;//加入标记      }    }    if (flag == 0)//如果没有交换过元素，则已经有序    {
             return;    }  }}

**插入排序算法**

思想步骤：

设数组为a\[0…n-1\]。

*  初始时，a\[0\]自成1个有序区，无序区为a\[1..n-1\]。令i=1
 *  将a\[i\]并入当前的有序区a\[0…i-1\]中形成a\[0…i\]的有序区间。
 *  i++并重复第二步直到i==n-1。排序完成。

算法实现：

void insertsort(int *array,int len){
        int i,j; int temp=-1; int k=-1; for(i=1;i<len-1;i++)   {
               k=i; //待插入位置        temp=array[k];        for(j=i-1;(j>=0)&&(array[j]>temp);--j)        {
                       array[j+1]=array[j]; //元素后移                 k=j;             }          array[k]=temp;   }}

**希尔排序算法**

思想步骤：

通过将待排序的元素分为若干个子序列，利用直接插入排序思想对子序列进行排序。然后将该子序列缩小，接着对子序列进行直接插入排序。按照这种思想，直到所有元素都按照关键字有序排列。

算法实现：

void ShellInsert(SqList *L, int c) /*对顺序表L 进行一次希尔排序，c 是增量*/{
       int i, j;DataType t;for(i=c+1; i<=L->length; i++) /*将距离为c 的元素作为一个子序列进行排序*/{
       if(L->data[i].key < L->data[i-c].key)/*若后者小于前者，则需移动元素*/{
       t = L->data[i];for(j=i-c; j>0&&t.key<L->data[j].key; j=j-c)L->data[j+c] = L->data[j];L->data[j+c] = t; /*依次将元素插入到正确的位置*/}}}void ShellInsertSort(SqList *L, int delta[], int m)/*希尔排序，每次调用算法ShellInsert，delta 是存放增量的数组*/{
       int i;for(i=0; i<m; i++) /*进行m 次希尔插入排序*/{
       ShellInsert(L, delta[i]);}}

**快速排序算法**

快速排序采用分治策略，是冒泡排序的一种改进算法。

思想步骤：

先从数列中取出一个数作为基准数（枢轴）。分区过程将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

再对左右区间重复第二步，直到各区间只有一个数。

void Qsort(int arr[], int low, int high){
           if (high <= low) return;    int i = low;    int j = high + 1;    int key = arr[low];    while (true)    {
               /*从左向右找比key大的值*/        while (arr[++i] < key)        {
                   if (i == high){
                       break;            }        }        /*从右向左找比key小的值*/        while (arr[--j] > key)        {
                   if (j == low){
                       break;            }        }        if (i >= j) break;        /*交换i,j对应的值*/        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    /*中枢值与j对应值交换*/    int temp = arr[low];    arr[low] = arr[j];    arr[j] = temp;    Qsort(arr, low, j - 1);    Qsort(arr, j + 1, high);}

**归并排序算法**

归并排序是建立在归并操作上的一种有效的排序算法。

思想步骤：

假设元素的个数是n，将每个元素作为一个有序的子序列，然后将相邻的两个子序列两两合并，得到n/2个长度为2 的有序子序列。继续将相邻的两个有序子序列两两合并，得到n/4个长度为4 的有序子序列。依次类推，重复执行以上操作，直到有序序列合并为 1 个为止。

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){
           int i = startIndex, j=midIndex+1, k = startIndex;    while(i!=midIndex+1 && j!=endIndex+1)    {
               if(sourceArr[i] > sourceArr[j])            tempArr[k++] = sourceArr[j++];        else            tempArr[k++] = sourceArr[i++];    }    while(i != midIndex+1)        tempArr[k++] = sourceArr[i++];    while(j != endIndex+1)        tempArr[k++] = sourceArr[j++];    for(i=startIndex; i<=endIndex; i++)        sourceArr[i] = tempArr[i];}

//内部使用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex){
           int midIndex;    if(startIndex < endIndex)    {
               midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int        MergeSort(sourceArr, tempArr, startIndex, midIndex);        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);    }}

![20210606111446596.png][]

[20210606111446596.png]: /images/20221005/5193eb761222434c81e4bd34965fd5d7.png