排序算法总结-01

插入排序

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序与打扑克时整理手上的牌非常类似。当你拿起一把乱牌的时候,摸来的第1张牌无须整理,从第二张开始,你会把它插入到前面已经整理好的序列中的合适位置。当然,整理扑克牌你可以直接进行插入,但到了编程的时候,你就需要有一个合理的方法找到它应该存放的位置。常见的方法是:待排序的数字a[i]如果大于左边的数字a[i-1],则说明可以继续向下进行来比较a[i+1]与a[i]的大小关系;若a[i]小于a[i-1],则交换a[i]与a[i-1]的值,继续向前比较a[i-1]与a[i-2]的大小关系.因此,插入排序的伪代码如下:

void Insertion(int arr[],int arrLength)
{
 int i = 1;
 while(i <= arrLength-1)
 {
  int j = i -1;
  while(j >= 0 && arr[j] > arr[j+1])
  {
   arr[j] = arr[j]^arr[j+1];
   arr[j+1] = arr[j]^arr[j+1];
   arr[j] = arr[j]^arr[j+1];
   j--;
  }
  i++;
 }
}

插入排序适用于待排数组基本有序的情况,它的最优时间复杂度是O(n),最差为On2).

插入参考代码:https://github.com/saymagic/sort/blob/master/insertion/insertion.c

选择排序

选择排序相比于归并,快速等排序算法应该算是比较简单的排序算法了,它的基本思想就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。和插入排序类似,它们都是从未排序的数组中选出数据分配到已排序的数组当中。插入式从未排序的数组中选第一号元素进行插入,而选择则是从为排序的数组中选出最小的排在已排序的数组后面。效率都是o(n2),但插入因为有一些剪枝,所以某些情况会更快速。

选择排序的参考代码:https://github.com/saymagic/sort/blob/master/select/select.c

归并排序

归并排序是利用递归和分而治之的技术将数据序列划分成为两个半子表,然后再将两个半子表合称为一个整表。那两个半子表怎么排序呢?继续按照上面的思想递归下去,递归终止的条件就是半子表不可继续分割。

其主要思想分为两部分,先分,后合。

归并算法首先将需排序的数组分为前后两部分,在对前后两部分继续分为前后两部分,直到分成每个部分只有一个数值,此时,在对其进行合并。看起来很难理解,但用递归的思想来考虑就很简单,其伪代码如下:

void mergeSort(int arr[],int start,int end, int cacheArr[] )
{
 if(start<end)
 {
  int mid = (start+end)/2;
  mergeSort(arr,start,mid,cacheArr);
  mergeSort(arr,mid+1,end,cacheArr);
  mergeArray(arr,start,mid,end,cacheArr);
 }
}

如果你对递归思想稍有了解的话,应该不难理解,我们先对arr数组的前半部分继续采用mergeSort排序,后半部分也采用mergeSort排序,最后将排好序的两个部分用mergeArray函数做一个合并。 </br>如果单从时间角度来考虑,归并排序应该是效率相当不错的了。最好为线性复杂度,最差为O(nLogn)。但归并排序的缺点就在于空间上表现不佳,最差需要O(n)的空间复杂度。

归并参考代码:https://github.com/saymagic/sort/blob/master/merge/merge.c

快速排序

都说快排效率好,那快排为啥这么快呢?快排和归并算法一样,同样采取递归的思想,大致如下:

从待排数组中选取一个基数,一般选取a[0],然后,快排要做的事情是,把所有小于基数a[0]的值全部放在左边,把全部大于a[0]的值放在右边,把自己放在中间。这样就形成x小与a[0]小于y的形式,接下来递归下去,将x、y两部分也这样排序,最终,整个待排数组就会按照大小个排好。

因此,快排的伪代码如下:

void QuickSort(int arr[],int left,int right)
{
 ajustArr(arr,left,right)
  arr[i] = x;
  QuickSort(arr, left, i-1);
  QuickSort(arr, i+1, right);
 }
}

仔细分析下应该很好理解,这里有难度的就是ajustArr函数,也就是怎样将数组按照基数分成两部分呢?一般采用的方法是从数组两边一次寻找,从左边找到比一个基数大的,再从右边找到一个比基数小的,然后俩数交换,这样,当左右碰头时目标是已经完成遍历。

速排序具有最好的平均性能(average behavior),但最坏性能(worst case behavior)和插入排序相同,也是O(n^2)。

快排参考代码:https://github.com/saymagic/sort/blob/master/quick/quick.c

堆排序

说起堆排序,首先得从二叉堆说起,那么什么是二叉堆呢?二叉堆的定义就是一种递归的思想:

  1. 父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  2. 每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

那么我们怎么来存储堆呢?

我们可以用数组来表示二叉堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

根据二叉堆的定义我们可以知道,最大堆的0号结点就是整个数组的最大值,同理,最小堆的0号结点就是数组的最小值。堆排序的思想就是,对有大小为n的待排序数组,整理成为二叉堆,每次将二叉堆的0号结点数值与n号结点交换,然后将新的堆整理成为二叉堆,n值减一后继续上述操作,知道n值为0.

堆排序也是一种插入排序,类似冒泡排序,每次都会选取最大的值来放进数组,但堆排序的效率要大于冒泡,因为它会过滤很多无用的比较。它的性能为0

堆排序参考代码:https://github.com/saymagic/sort/blob/master/heap/heap.c


image           image
章节列表