在黑马的基础视频里讲到了两种排序的方式。经过自己的学习经验，跟大家分享几个高效率的排序方式。我们在提及代码的效率的时候，我提一下两个概念，一个叫时间复杂度O(n)，一个叫空间复杂度f(n)。简单的讲时间复杂度是计算机执行代码时所用的时间，而空间复杂度是计算机执行代码时所使用的内存空间。
1、学习资料里提到的冒泡排序

1. void maopao(int arr[])
   
2. {
   
3.     int temp=0;
   
4.     for (int i=0; i<N; i++) {
   
5.         for (int j=0; j<N-1-i; j++) {
   
6.             if(arr[j]>arr[j+1]){
   
7.                 temp=arr[j];
   
8.                 arr[j]=arr[j+1];
   
9.                 arr[j+1]=temp;
   
10.             }
    
11.         }
    
12.     }
    
13. }

复制代码

2、学习资料里提到的选择排序

1. void selectSort(int arr[])
   
2. {
   
3.     int temp;
   
4.     for (int i=0; i<N; i++) {
   
5.         for (int j=i+1; j<N; j++) {
   
6.             if (arr[i]>arr[j]) {
   
7.                 temp=arr[j];
   
8.                 arr[j]=arr[i];
   
9.                 arr[i]=temp;
   
10.             }
    
11.         }
    
12.     }
    
13. }

复制代码

3、插入排序

1. void insertSort(int arr[])
   
2. {
   
3.     int temp,j,p;
   
4.     for (int i=0; i<N; i++) {
   
5.         j=i-1;
   
6.         p=arr[i];
   
7.         while (j>=0&&arr[j]>p) {
   
8.             arr[j+1]=arr[j];
   
9.             j--;
   
10.         }
    
11.         arr[j+1]=p;
    
12.     }
    
13. }

复制代码

以上3个排序方式是比较低效率的，但由于比较容易理解和书写，使用率还是比较高的。
上述3种排序的空间复杂度都是f(N)；时间复杂度冒泡[O(n*n/2)]=选择[O(n*n/2)]>插入[O(n)~~O(n*n/2)]。
下边我整理一下快速排序，归并排序和堆排序的代码，有兴趣的可以看一下。

插入排序的思想是什么

将当前元素插入到已有序列的数组中，冒泡。举例说明：
数据内容是 1 4 3 2 5;
for i = 1-5;
i=1时 当前元素是1；无有序数组，1插入数组，形成长度为1的有序数组。
i=2时 当前元素是4，有序数组是 1，4插入到有序数组的最后，形成1 4，4>1，位置不变，结束本次操作
i=3时 当前元素是3，有序数组是 1 4，3插入到有序数组的最后，形成 1 4 3，3<4,3和4交换位置，形成1 3 4，3>1位置不变，结束本次操作。i=4时 当前元素是2，有序数组是 1 3 4, 2插入到有序数组的最后，形成 1 3 4 2，2<4，交换2和4的位置，形成1 3 2 4，2<3交换2和3的位置，形成1 2 3 4，2>1，位置不变，结束本次操作。
i=5时 当前元素是5 有序数组是1 2 3 4，5插入到有序数组的最后，形成1 2 3 4 5,5>4，位置不变，结束本次操作。
总结一下就是，将arr[i]插入到有序数组的最后，然后和前边的元素比较，如果小于前一个元素，那么交换位置，直到大于前一个元素，结束操作。
虽然在结构上，和冒泡排序多少有点类似，但在计算的过程中，发现在形成新的有序数组的时候，当前元素找到新的有序数组的位置的时候，能减少后续的操作。
假设已有数组恰好是一个有序数组，那么在生成新的数组的时候，只需要做一次操作。这是，插入排序的时间复杂度就是O(n)。反之，假设已有数组是一个反序数组，那么在生成新的数组的时候，都需要当前元素和有序数组的每个元素做比较，这样就跟冒泡排序没有差别。