转载

冒泡以及插入排序算法的改进

冒泡排序

说明：此文中的排序算法数组，第一个数(即0下标)没有作为数据处理(i从1开始)，arr[0]用作哨岗，部分排序算法（如插入排序）比较时需要用到

排序思想：

1.假设共有N个数，从头开始，比较相邻的两个数，如果前一个数比后一个数大，则交换位置，否则不变，继续比较。

2.按照这样的方法对数组从0到N-1进行遍历，一轮遍历完，则最后一个数为最大值。

3.N=N-1,按照1,2的思想遍历N-1轮，则数组从大到小排序成功

void Popsort(int arr[],int n)//冒泡排序 {  int i,j,temp;  for(i = 1;i < n;i++)  {   for(j = 2;j < n - i + 1;j++) //注意：此处排序是从数组的下标1开始   {    if(arr[j-1] > arr[j])    {     temp = arr[j-1];     arr[j-1] = arr[j];     arr[j] = temp;    }   }  } }

下面对算法进行优化

改进版冒泡排序：

如果数组中有50个数，后20个已经有序且大于前面30个数，则一轮遍历完成，最后一个发生交换的位置肯定小于30，并且后面的数一定有序。

我们如果记下这个位置，然后遍历到此就结束此轮遍历比较，则算法会优化很多。

void PopsortPro(int arr[],int n)//改进版冒泡排序 {  int i,exchange = n,temp;  while(exchange)  {   n = exchange;   exchange = 0; //最后一次交换的位置置为0,若无交换，排序完成   for(i = 2;i < n;i++)   {    if(arr[i-1] > arr[i])    {     temp = arr[i];     arr[i] = arr[i-1];     arr[i-1] = temp;     exchange = i;  //记下最后一次交换的位置    }   }  } }

插入排序

排序思想：

1.把第一个数据当做有序的，即为有序区，后面的数据当做无序的，为无序区。

2.然后从无序数据中从第一个开始，不断按大小插入有序数据中。

3.i++,不断按2的方法循环，直到i==n-1,排序完成。

void InsertSort(int arr[],int n)//直接插入排序 {  int i,k;  for(i = 2;i < n;i++)  {   arr[0] = arr[i];  //arr[0]记录要插入的数   k = i - 1;   while(arr[k] > arr[0]) //找插入位置   {    arr[k+1] = arr[k]; //把数不停后移    k--;   }   arr[k+1] = arr[0];  } }

改进版插入排序

因为插入的过程就是用无序区的数据在有序区做有序插入，其中就包含一个查找插入位置的过程，上述算法的查找方式为暴力查找，直接从尾部找到头部。

我们可以在查找插入位置的这一过程中做优化，使用效率更高的折半查找，可以优化算法效率。

上面的插入排序是边查找插入位置，边移动数据，如果利用折半查找插入位置，则是先找到位置，然后统一移动数据。

void Insert_halfsort(int arr[],int n)//折半插入排序 {  int i,j,low,high,mid;  for(i = 2;i < n;i++)  {   arr[0] = arr[i];   high = i - 1;   low = 1;   while(low <= high)   {    mid = (low + high)/2; //折半查找    if(arr[mid] < arr[0])  //右半区域    {     low = mid + 1;    }    else     //左半区域    {     high = mid - 1;    }   }       //插入点即为high+1      for(j = i;j > high+1;j--) //将数据后移，空出位置填充无序数据   {    arr[j] = arr[j-1];   }   arr[high + 1] = arr[0];  } }

可以明显看到，利用折半查找的插入排序，代码量比直接插入排序多了一倍，不过在查找的过程中效率较高，数据移动个数是一致的。

不过这种优化没有什么大的改进，时间复杂度仍然是O(n^2)。

选择排序

这种算法和冒泡，插入排序效率差不多，时间复杂度都是O(n^2)。

冒泡排序主要操作在于交换，插入排序主要操作在于查找和移动数据，而选择排序则主要是大量的比较。

排序思想：

1.在一堆无序数据中通过遍历比较找到最小的数，放在第一个位置。

2.在剩下的无序数据中找到最小的数，放在第二个位置。

3.不断找到最小的数，最后一个最小值即放在最后一个位置。

void ChooseSort(int arr[],int n)//选择排序 {  int i,j,min,temp;  for(i = 1;i < n;i++)  {   min = i;   for(j = i + 1;j < n;j++)   {    if(arr[j] < arr[min])    {     min = j;    }   }   if(min != i)   {    temp = arr[min];    arr[min] = arr[i];    arr[i] = temp;   }  } }