阿包说算法之排序

　　排序的方法有很多，本文主要介绍三种：冒泡排序，快速排序，归并排序。在很多算法中，都会用到递归算法，因此递归不再单独讲。1.冒泡排序
　　算法思路
　　冒泡排序的思想是最符合常人思维的，比如一个数组：3,6,8,2,1。首先选择第一个数3，然后从后面的数开始遍历，如果比数组第一个数 小，就交换位置，否则继续： 比如，第一次比较3和6，3小，继续，3和8比，继续，3和2比，2小，就交换3和2的位置，数组变成2,6,8,3,1，这时数组第一个数 是2，2和1比，1小，交换2和1的位置，变成1,6,8,3,2，此时第一轮遍历结束，可以看到一轮遍历可以把最小的数选出。
　　第二次从第2个数开始遍历，与后面的数比较，就是6依次和8,3比，跟3换位置，然后3和2比，又换位置，次轮结束后1,2,8,6,3。继续下一轮，直到遍历结束。可见第一次把最小的数放到第一位，第二次把第二小的数放到第二位，第N次把第N小的数放到第N位。void BubbleSort(int* arr, int counts)  {     int tmp = 0;     for (int i = 0; i < counts-1; i++)     {         for (int j = i+1; j < counts; j++)         {             //如果后面的数比前面的小，就交换位置             if (arr[i] > arr[j])              {                 tmp = arr[i];                 arr[i] = arr[j];                 arr[j] = tmp;             }         }     } }  int main()  {     int arr[] = {7,3,8,2,9,6,0,2,4,7};     BubbleSort(arr, 10);     for (int i = 0 ; i<10; i++)         cout << arr[i];     return 0; }
　　最终输出
　　0223467789
　　说明：冒泡排序的时间复杂度为O(N^2)，冒泡排序写法可能不一定是跟上面的一样，但是思想是一致的2.快速排序
　　算法思路
　　快速排序法的思想是把数组的第一个数取出来作为分界点，让数组中小于他的数放在他左边，大于他的数放在他右边，比如 53974这组数字，选5为分界点，然后让34在5左边，97在5右边，变成34597 然后，对左右两部分34和97，分别继续重复上面的步骤，直到有序。这里可以看出应该用到递归 。
　　步骤如下，有一串数字3,6,8,2,7，首先把第一个数3取出来作为分界点，然后从最右边开始找小于3的数，7大于3跳过，继续看2，2小于3，就把2放到3的位置，2的位置空出来【2,6,8,,7】，再从左边开始，6大于3，就把6放到原来2的位置，6的位置空出来【2,,8,6,7】，再从右边8开始，8大于3跳过，下一个，是空了，则此轮结束，把3放到空位【2,3,8,6,7】。
　　然后对3左右两边的2和8,6,7分别按上面的步骤进行排序，就变成【2,3,6,7,8】void FastSort(int* arr, int counts) {     if (counts == 1)         return;          int num = arr[0]; //取数组的第一个数字作为分界点     int nullPos = 0; //空位在此     int left = 1, right = counts-1; //左右开始的位置          while (true)     {          //从右边开始找，直到有小于num的, 或者遇到空位就结束         while (right != nullPos && arr[right] >= num)             right--;                  if (right == nullPos) //结束了             break;                  //否则就是找到了小的         arr[nullPos] = arr[right];         nullPos = right;          //再从左边找，左边的得大于num才挪         while (left != nullPos && arr[left] <= num)              left++;                  if (left == nullPos) //结束了             break;          arr[nullPos] = arr[left]; //当前值放到空位         nullPos = left;     }     //跳出了，把num放到空位     arr[nullPos] = num;      if (nullPos > 0) //有前半段         FastSort(arr, nullPos); //前半段排序     if (nullPos < counts-1) //有后半段         FastSort(arr+nullPos+1, counts-nullPos-1); //后半段排序 }  int main()  {     int arr[] = {7,3,8,2,9,6,0,2,4,7};     FastSort(arr, 10);     for (int i = 0 ; i<10; i++)         cout << arr[i];     return 0; }
　　最终输出
　　0223467789
　　说明：这种排序的方式是一种分治 的思想，把大问题拆分成多个解法一样的小问题，这里是把大数组拆成前后2个解法一样的小数组，分成两部分的分治法又叫二分法，但是跟下面的二分法排序又不一样。
　　另外，快速排序代码会有多种不同的写法，但是思想是一致的，快速排序中有2个while，在极端情况下（比如数组是有序的，会遍历整个数组）的算法复杂度是O(N^2)，一般情况下是O(NlogN)，但实际上乱序的情况下，很快就能跳出while，所以被称为快速排序，此排序最实用，请读者牢记。3.归并排序（二分法排序）
　　算法思路
　　归并排序思路是：将数组一分为二，再对分出来的2个子数组继续拆分，2分，拆分直到子数组只有一个数字，然后把所有的数字两两组合成有序小数组，最后合成一个完整数组，是典型的二分法，所以又叫做二分法排序
　　这里的思想是拆分后就变成有序数组（一个数字肯定有序），然后就是对有序数组的合并操作。比如83652，拆分成836,52,继续拆分成8,3,6,5,2。然后8和3组合成38, 38和6组合成368， 52组合成25,。最后把368和25组合成23568。void Merge(int* arr1, int counts1, int* arr2, int counts2, int* merge) {     //开始组合     int i=0, j=0, pos=0;          //较小的数给tmp,小的指针++，tmp指针++     while (i < counts1 && j < counts2)         merge[pos++] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];           //跳出，如果某个数组还有，加到tmp后面     while (i < counts1)         merge[pos++] = arr1[i++];      while (j < counts2)         merge[pos++] = arr2[j++]; }  void Sort(int *arr, int counts, int* out) {     if (counts == 1) //返回条件     {         out[0] = arr[0];         return;     }               int mid = counts/2; //中点作为拆分点     int* out1 = new int[mid];     int* out2 = new int[counts-mid];      Sort(arr, mid, out1); //左边排序     Sort(arr+mid, counts-mid, out2); //右边排序     Merge(out1, mid, out2, counts-mid, out); //左右合并      delete []out1;     delete []out2; }  void MergeSort(int *arr, int counts) {     int* out = new int[counts];     Sort(arr, counts, out);     for (int i=0; i　　说明：归并排序用的是二分法，把数组分成2个子数组分别排序，实际上可以用三分法四分法，把数组分成3个子数组，4个子数组等都可以，读者可以自行思考如何使用三分法归并排序。
　　归并排序的时间复杂度是O(NlogN)