更多精彩文章请关注公众号『大海的BLOG』

简介

排序的归纳以及时间复杂度表
排序时间复杂度

冒泡排序

冒泡排序是一个比较简单的排序，它是一次比较相邻两个元素的值，如何顺序错误就交换两个数的位置，一直到没有交换的数为止，排序结束。

若对n个数进行排序，我们需要n-1次比较，所以第k次比较需要进行n-k次比较。>

排序算法通过以数据对象的两两比较作为关键所以可以得出，冒泡排序需要进行的比较次数为：(n-1) + (n-2) + … + 1 = n(n-1) / 2。
因此冒泡排序的 *时间复杂度为O(n^2)**

算法

  1. 比较相邻的元素，前一个比后一个大（或者前一个比后一个小）调换位置
  2. 每一对相邻的元素进行重复的工作，从开始对一直到结尾对，这步完成后，结尾为做大或最小的数
  3. 针对除了最后一个元素重复进行上面的步骤。
  4. 重复1-3步骤直到完成排序

动图演示：
演示1

//冒泡排序 从小到大
#include <stdio.h>

void bubble_sort(int *arr, int n)
{
    int i,j;
     for(i = 0; i < n-1; i++)
     {
          for(j = 0; j < n-i-1; j++)
          {
               if(arr[j] > arr[j+1])
               {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
               } 
          }
    }
}

int main()
{
    int i;
     int arr[]={0,2,1,3,4,6,5,7,9,8};
     int n = sizeof(arr) / sizeof(int);
     bubble_sort(arr,n);
     for(i = 0; i < n; i++)
     {
          printf("%d ",arr[i]);
     }
     printf("\r\n");
     return 0;
}

程序运行结果
冒泡排序

选择排序

选择排序共需要的比较次数为n*(n-1) / 2，因此选择排序算法的时间复杂度与冒泡排序一样，也为O(n^2)

算法简介：

  1. 初始状态：序列为无序状态。

  2. 第1次排序：从n个元素中找出最小(大)元素与第1个记录交换

  3. 第2次排序：从n-1个元素中找出最小(大)元素与第2个记录交换

  4. 第i次排序：从n-i+1个元素中找出最小(大)元素与第i个记录交换

  5. 以此类推直到排序完成

    动图演示
    演示2

//选择排序 从大到小
#include <stdio.h>
//函数申明
void choice (int * a, int n );
void show ( int *a, int n );

int main ( )
{
    int arr[10] = {1,3,2,4,6,5,7,8,9};
    show(arr, 10);
    choice(arr, 10);
    show(arr, 10);
    return 0;
}

//选择排序
void choice ( int *a, int n )
{
    int i , j ,tmp;
    for (i = 0; i < n - 1; i++)
    {
       for (j = i + 1; j < n; j++)
       {
           if (a[i] < a[j])
           {
             tmp = a[i];
             a[i] = a[j];
             a[j] = tmp;
           }
      }
    }
}

//显示
void show (int * a, int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf ("%d ", a[i]);
    }
    printf("\r\n");
}

运行结果
运行结果

插入排序

插入排序是一个比较直观的算法，对于n个元素，一共需要进行n-1轮比较，而第k轮比较需要进行k次数组元素的两两比较，因此共需要进行的比较次数为：1 + 2 + … + (n-1)，所以插入排序的时间复杂度同冒泡排序一样，也为O(n^2)

算法简介：

  1. 从第一个元素开始，该元素可认为已排序。
  2. 取出下一个元素，在排序好的元素序列中从后往前扫描
  3. 如果元素(已排序)大于新元素，将该元素移到下一位置
  4. 重复3.直到找到已排序的元素小于或等于新元素的位置
  5. 将新元素插入该位置后
  6. 重复2-5直到排序完成

动图演示
演示3

代码部分

//插入排序(从小到大) 
#include<stdio.h>

//定义一个插入函数"insertion_sort" 
void insertion_sort(int *number,int n)    
{
    int i=0,ii=0,temp=0;  
     //循环遍历 
    for(i=1;i<n;i++) 
    {
        //将temp每一次赋值为number[i] 
        temp=number[i];  
        ii=i-1;  
        //这里改顺序 (temp后的)"<"为小到大，">"为大到小 ！！！
        while(ii>=0&&temp<number[ii])   
        {
            //将大的元素往前放 
            number[ii+1]=number[ii];   
            ii--; 
        }
        number[ii+1]=temp;   //与"number[ii+1]=number[ii];"一起意为 
    }              //如果插入的数比之前的大,将number[ii]与number[ii+1]互换 
}

int main() 
{
   int i;
  int arr[]={2,0,1,3,4,6,5,7,9,8};
  int n = sizeof(arr) / sizeof(int);
  insertion_sort(arr,n);
  for(i = 0; i < n; i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\r\n");
  return 0;
}

运行结果
运行结果

更多精彩文章请关注公众号『大海的BLOG』

赏

学习中...