排序 之 快排、归并、插入 - <时间复杂度>----掌握思想和过程

　　俗话说：天下武功无坚不破，唯快不破。对于算法当然也是要使用时间最短、占用空间最小的算法来实现了。

　　注意：我代码里面打的备注仅供参考，建议不要背模板（因为没有固定的模板），可以写一个数列按着代码跑两圈或者把代码改一下输出每次排序后的结果。

　总之，师傅领进门，修行在个人。奋斗把！骚年！

※冒泡排序、选择排序：（不稳定，时间复杂度 O(n^2)）

 #include "cstdio"
 #include "iostream"
 using namespace std;

 void bubble_sort (int *a, int n) {
     int t;
     for (int i = ; i < n - ; ++i) {
         for (int j = ; j < n - i - ; ++j) {
             if (a[j] > a[j + ]) {
                 t = a[j];
                 a[j] = a[j + ];
                 a[j + ] = t;
             }
         }
     }
 }

 int main () {
     int n, a[];
     cin >> n;
     for (int i = ; i < n; ++i)
         cin >> a[i];
     bubble_sort (a, n);
     for (int i = ; i < n; ++i)
         cout << a[i] << " ";
     cout << endl;
     return ;
 }

bubble sort

 #include "cstdio"
 #include "iostream"
 using namespace std;

 void selection_sort (int *a, int n) {
     int t;
     for (int i = ; i < n; ++i) {
         for (int j = i; j < n; ++j) {
             if (a[i] > a[j]) {
                 t = a[j];
                 a[j] = a[i];
                 a[i] = t;
             }
         }
     }
 }

 int main () {
     int n, a[];
     cin >> n;
     for (int i = ; i < n; ++i)
         cin >> a[i];
     selection_sort (a, n);
     for (int i = ; i < n; ++i)
         cout << a[i] << " ";
     cout << endl;
     return ;
 }

selection sort

　　如果说冒泡和选择排序都没有弄明白的话，那你对于排序可以只记个C++STL中的sort函数和头文件就行了。

　　#include <algorithm>

　　sort (要排序数组的首地址， 要排序一共的个数);

　　//  默认是升序，如果想要降序的话，写一个compare函数   bool compare(int a, int b) { return a > b;}

　　// a < b;升序   a > b;降序

 #include <iostream>
 #include <algorithm>
 using namespace std;

 int cmp(int a, int b) {
     return a > b;
 }

 int main () {
     int a[] = {, , , , };
     // sort (a, a+5, [](int a, int b){return a > b;});
     // 这是闭包的格式， 适合函数体较短的时候使用。

     sort (a, a+, cmp);

     for (int i = ; i < ; ++i) {
         cout << a[i] << " ";
     }
     cout << endl;
     return ;
 }

C++ STL sort

　　sort排结构体（可以使用pair更方便）

 #include <iostream>
 #include <algorithm>
 #include <cstdio>
 using namespace std;

 struct node {
     int x, y;
 }t[];

 bool cmp (const node a, const node b) {
     if (a.x > b.x) {
         return ;
     } else if (a.x==b.x && a.y<b.y) {
         return ;
     } else {
         return ;
     }
 }

 int main () {
     t[].x = ;
     t[].y = ;

     t[].x = ;
     t[].y = ;

     t[].x = ;
     t[].y = ;

     t[].x = ;
     t[].y = ;

     t[].x = ;
     t[].y = ;

     t[].x = ;
     t[].y = ;

     sort (t, t+, cmp);
     for (int i = ; i < ; ++i) {
         cout << t[i].x <<  ' ' << t[i].y << endl;
     }
     return ;
 }

 /*
 3 2
 2 3
 1 1
 1 2
 1 3
 2 1
 */

sort排结构体数组

※基础快排1----选择左右两边为基准排序：（不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)）

 #include <bits/stdc++.h>//万能头文件
 using namespace std;

 void quick_sort (int a[], int l, int r) {
     if (l >= r) return ;
     int i = l, j = r;
     int key = a[l];
     while (i < j) {    ///这里不能带等号，，死循环
         while (i < j && a[j] >= key) {//<=是找有相同数字的时候
             j --;    //选的左边作为key，所以就从右边开始.
         }
         a[i] = a[j];    //找到一个该交换的时候退出交换。
         while (i < j && a[i] <= key) { //<=是找有相同数字的时候
             i ++;
         }
         a[j] = a[i];    //同上
     }
     a[i] = key;
     quick_sort (a, l, i - );////应该可以交换位置，因为这两个是等效的，
     quick_sort (a, i + , r);////就是排序上次key两的的值
 }

 int main () {
     int n;
     int a[];
     scanf ("%d", &n);
     for (int i = ; i < n; ++i)
     {
         scanf ("%d", &a[i]);
     }
     quick_sort (a, , n - );
     for (int i = ; i < n; ++i)
     {
         printf("%d ", a[i]);
     }
     printf("\n");
     return ;
 }

Quick_sort_by_left

 #include <bits/stdc++.h>
 using namespace std;

 void quick_sort (int a[], int l, int r) {
     if (l >= r) return ;
     int i = l, j = r;
     int key = a[r];
     while (i < j) {    ///这里不能带等号，，死循环
         while (i < j && a[i] <= key) {//<=是找有相同数字的时候
             i ++;    //选的右边作为key，所以就从左边开始.
         }
         a[j] = a[i];    //找到一个该交换的时候退出交换。
         while (i < j && a[j] >= key) { //<=是找有相同数字的时候
             j --;
         }
         a[i] = a[j];    //同上
     }
     a[j] = key;//-----先替换的a[j]，所以在这里补上.
     quick_sort (a, l, i - );////可以交换位置，是等效的
     quick_sort (a, i + , r);////就是排序上次key两的的值
 }

 int main () {
     int n;
     int a[];
     scanf ("%d", &n);
     for (int i = ; i < n; ++i)
     {
         scanf ("%d", &a[i]);
     }
     quick_sort (a, , n - );
     for (int i = ; i < n; ++i)
     {
         printf("%d ", a[i]);
     }
     printf("\n");
     return ;
 }

Quick_sort_by_right

　　注意：快排函数最后递归的时候可以按j也可以按i，因为最后满足 i == j; 理解代码里面等号的取舍！

※基础快排2----选择任意数字为基准排序：（不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)）

 #include <cstdio>
 #include <iostream>
 using namespace std;

 void quick_sort (int *a, int l, int r) {
     int i = l, j = r, key = a[l + (r - l) / ];
     //int key = a[r];
     //从数列里面任意找一个key就行
     int t;
     while (i < j) {
         while (i < r && a[i] < key)    i ++;
         //不能写成a[i] <= key，会跳过一些数字,导致不能排序
         while (j > l && a[j] > key)    j --;
         //这两个while可以交换位置，以左右为基准的快排不能交换
         if (i <= j) {
             t = a[i];
             a[i] = a[j];
             a[j] = t;

             i ++;
             j --;
         }
     }
     if (i < r)    quick_sort (a, i, r);
     if (j > l)    quick_sort (a, l, j);
 }

 int main () {
     int n;
     int a[];
     cin >> n;
     for (int i = ; i < n; ++i)
         cin >> a[i];
     quick_sort (a, , n - );
     for (int i = ; i < n; ++i)
         cout << a[i] << " ";
     cout << endl;
     return ;
 }

 Quick_sort_anyone

Quick_sort_by_anyone

简述：快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

***另外一种快排的写法（从蓝桥杯上学习到的，思想都是一样的，只是实现有点不一样）

 #include <stdio.h>

 void swap(int a[], int i, int j)
 {
     int t = a[i];
     a[i] = a[j];
     a[j] = t;
 }

 int partition(int a[], int p, int r)
 {
     int i = p;
     int j = r + ;
     int x = a[p];
     while(){
         while(i<r && a[++i]<x);
         while(a[--j]>x);
         if(i>=j) break;
         swap(a,i,j);
     }
     swap(a, p, j);
     return j;
 }

 void quicksort(int a[], int p, int r)
 {
     if(p<r){
         int q = partition(a,p,r);
         quicksort(a,p,q-);
         quicksort(a,q+,r);
     }
 }

 int main()
 {
     int i;
     int a[] = {,,,,,,,,,,,};
     int N = ;

     quicksort(a, , N-);

     for(i=; i<N; i++) printf("%d ", a[i]);
     printf("\n");

     return ;
 }

蓝桥杯

※基础快排3----调用stdlib.h中的qsort函数。

　　语法：

　　#include <stdlib.h>

　　void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

　　buf: 要排序片段的首地址。

　　num: 要排序片段的个数。

　　size:要排序元素占的字节，可以使用sizeof来求。

　　compare：如果函数compare 的第一个参数小于第二个参数，返回负值（升序）；如果等于返回零值（不变）；如果大于返回正值（降序）(函数参数必须为const void *类型)。

 #include <stdio.h>
 #include <stdlib.h>

 int cmp(const void *a, const void *b) {
     return *(char*)a - *(char*)b;
     // 如果数组是int类型的话，这里的char就是用int
     // 下面对应sizeof(int).
 }

 int main() {
     char b[] = {""};
     qsort(b, , sizeof(char), cmp);
     printf("%c", b[]);
     for(int i = ; i < ; i++)
         printf(" %c", b[i]);
     printf("\n");
     return ;
 }

Qsort

※归并排序：（稳定，时间复杂度 O(nlog n)）

 #include <stdio.h>//归并排序
 #include <stdlib.h>
 void merge(int a[],int b[], int f, int mid, int e)
 {//合并两个数组
     int i = f, j = mid + , k = f;
     while(i <= mid && j <= e)//注意衔接
     {
         if(a[i] >= a[j])    //谁大就不把谁装到前面
             b[k++] = a[j++];
         else
             b[k++] = a[i++];
     }
     while(i <= mid)//前半个有剩余
         b[k++] = a[i++];
     while(j <= e)//后半个有剩余
         b[k++] = a[j++];
     for(i = f; i <= e; i++)    //最后再还给a
         a[i] = b[i];
 }
 void mergesort(int a[], int b[], int f, int e)//内部使用递归
 {
     if(f < e)
     {
         int mid = (e + f) / ;
         mergesort(a, b, f, mid);    //拆分到很小很小
         mergesort(a, b, mid + , e);
         merge(a, b, f, mid, e);
     }
 }
 int main(){
     int n;
     int a[];
     int i, b[];
     scanf ("%d", &n);
     for (int i = ; i < n; ++i)
         scanf ("%d", &a[i]);
     mergesort(a, b, , n - );
     for(i = ; i < n; i++)
         printf("%d ", a[i]);
     printf("\n");
     return ;
 }

Order_by_merging

　简述：将数组拆分为两组，对于一个数组来说，两个数组要好排的多...依次类推，当分到只要一个元素的时候，我们就认为是有序的，然后再挨个合并相邻的数组。我们可以先递归分解，然后再归并排序。

※插入排序:

 /*
  *   > File Name: test.cpp
  *   > Author: Ddlm2wxm
  *   > Mail: [e-mail]
  *   > Created Time: 2016年10月20日 星期四 07时35分53秒
  *********************************************************/

 #include <iostream>
 #include <cstdio>
 using namespace std;

 void Insert_sort (int a[], int n) {
     int i, j;
     for (i = ; i < n; ++i) {
         int t = a[i];
         for (j = i-; j >= &&t<a[j]; --j)
             a[j+] = a[j];
         a[j+] = t;
     }
 }

 int main() {
     int n;
     int a[];
     cin >> n;
     for (int i = ;i < n; ++i) {
         cin >> a[i];
     }
     Insert_sort (a, n);
     for (int i =;i < n; ++i) {
         cout << a[i] << " ";
     }
     cout << endl;
     return ;
 }

Insert_sort

简述：个人认为插入排序是最简单的，就是从第一个开始，认为第一个数是有序的，然后依次取后面的数字，通过遍历前面的排序好了的数组寻找取到元素的位置。

　欢迎码友评论，一起成长。