文章目录

• 前言
• 五大算法介绍
  • 1.冒泡算法
  • 2.快速排序
  • 3.插入算法
  • 4.希尔算法
  • 5.选择算法

• 例题讲解

• 性能比较
• 总结

前言

排序算法（Sorting algorithm）是一种能将序列按照某种特定排序方式进行排列的一种算法，下面简要介绍其中五种排序算法。

五大排序算法

1.冒泡排序

冒泡排序是一种较简单的排序算法，又称起泡排序。其基本思路是，每次将相邻的两个，每次比较一轮，总会找到序列中最大的一个或最小的一个。最终可以得到一个递增数列或者递减数。

核心过程

void Bubble_sort(int a[],int n) { int i,j,temp; for(i=0;i<n-1;i++)//C语言中数组的下标是从0开始，故i最大为n-1 { for(j=0;ja[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }

2.快速排序

快速排序是基于冒泡排序的改进方法，其基本思路为：先在未排序的序列选择一个值，以该值为基准数，将序列一分为二，小于基准数的放于左边，大于基准数的放于右边，重复上述操作，当个区间只有一个数时结束。

核心过程

void quick_Sort(int a[], int low, int high){ if (low > high) {  return; } int i = low, j = high, temp = a[i];//temp为基准数 while (i < j) {  while (temp < a[j] && i < j){   j--;  }  if (i a[i] && i < j){   i++;}  if (i < j){   a[j--] = a[i];      } } a[i] = temp;//递归调用 quick_Sort(a, low, i - 1); quick_Sort(a, i + 1, high);}

3.插入排序

 插入排序是一种简单的排序算法，即在有序序列中，插入一些数据且插入后序列依旧为有序序列。

核心过程

void insertion_sort(int arr[], int n){ int i,j,k; for (i=1;i=0) && (arr[j]>k)) {   arr[j+1] = arr[j];   j--;  }  arr[j+1] = k; }}

4.希尔排序

希尔排序是基于插入排序而提出的方法的，其基本思想是：先将整个未排元素序列切割成分成若干个子序列，确定步长并分别进行插入排序，再减少一半步长同时进行上述操作，当每个子序列长度为1时，再进行一次插入排序，便可得到有序的序列。

核心过程

void shellSort(int a[], int len){    int i, j, k, temp, SL;  // 设SL为希尔步长    for (SL = len / 2; SL > 0; SL /= 2)  // 设置希尔步长的初始值为len的二分之一，完成一次遍历之后，步长减少一半{      for (i = 0; i < SL; ++i)  //  i 为每次分组的第一个元素下标 {  for (j = i + SL; j = 0 && a[k] > temp) {  a[k + SL] = a[k];   k -= SL;     }     a[k + SL] = temp;  }    }    }}

5.选择排序

选择排序是一种简单直观的排序算法，其基本思路：先在未排序的序列中找到最小（大）元素，并存放到序列的起始位置，再从剩余的未排序排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。一直重复上述过程，直到所有排序完成。

核心过程

void select_sort(int a[],int n)    {    int i,j,k,temp;for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++)     {     if(a[j]<a[k])     k=j;} if(k!=j)     {     temp=a[i];a[i]=a[k];  a[k]=temp; }    }} 

例题讲解

将下列数列进行排序 a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21}；

插入排序解法：

#include void select_sort(int a[],int n)    {    int i,j,k,temp;for(i=0;i<n-1;i++){ k=i; for(j=i+1;j<n;j++)     {     if(a[j]<a[k])     k=j;} if(k!=j)     {     temp=a[i];a[i]=a[k];  a[k]=temp; }    }}int main(){ int a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21};select_sort(a,20);for (int i=0;i<20;++i){printf("%d ",a[i]);} printf("\n"); return 0;} 

快速排序解法

#include void quick_Sort(int a[], int low, int high){ if (low > high) {  return; } int i = low, j = high, temp = a[i];//temp为基准数 while (i < j) {  while (temp < a[j] && i < j){   j--;  }  if (i a[i] && i < j){   i++;}  if (i < j){   a[j--] = a[i];      } } a[i] = temp;//递归调用 quick_Sort(a, low, i - 1); quick_Sort(a, i + 1, high);}int main(){ int a[20]={30,-19,-29,39,2,4,8,28,-3,40,51,39,78,43,20,31,27,55,68,21}; quick_Sort(a,0,20);for (int i=0;i<20;++i){printf("%d ",a[i]);} printf("\n"); return 0;} 

运行结果显示：

 性能比较

总结

冒泡算法，快速排序，插入算法，希尔算法和选择算法都是排序算法中常用的算法，其时间复杂度有所区别，当考虑算法的时间复杂度时，要合理的选择适当的排序算法。