我们更加排序记录是否全部放置在内存中，将排序分为内排序和外排序，这里我们主要了解七个经典的内排序：插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序。
对于一个问题，选择哪种排序方法主要从以下两方面进行考虑：
1.所选排序方法的时间复杂度。
2.所选排序方法的稳定性。
对于一些问题，排序的稳定与否至关重要，因此我们有必要了介绍下排序的稳定性： 通俗的说，对于待排序序列a[]，若有 a[i] == a[j]，a[i]的位置在a[j]前面，若排序后a[i]的位置仍然在a[j]前面，那么这种排序稳定，否则即为不稳定排序。
1.插入排序：
基本操作：将一个记录，插入到已经排好序的有序表中，从而得到一个新的，记录数增加1的有序表。
最优时间复杂度：当序列已经为有序时，时间复杂度为O(n)
最差时间复杂度：当序列为逆序时，时间复杂度为O(n^2)
稳定性：稳定
代码:
/插入排序/////void insert_sort(int a[],int n){ for(int i=1;i 0 && a[j-1]>temp) { a[j] = a[j-1]; j--; } a[j] = temp; }}
2.希尔排序：
基本操作：希尔排序是对插入排序改进。把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止（这里的增量可以理解为下标间隔）。
最优时间复杂度：O(nlogn)
最差时间复杂度：O(n^2)
稳定性：不稳定
代码：
///希尔排序//void shell_sort(int a[],int n){ for(int d=n/2;d>0;d/=2) { for(int i=d;i =d && a[j-d]>temp) { a[j] = a[j-d]; j -= d; } a[j] = temp; } }}
3.选择排序：
基本操作：在未排序的序列中找到一个最大/最小值，将其放在已排序的序列的末尾。
最优时间复杂度：O(n^2)
最差时间复杂度：O(n^2)
稳定性：稳定
代码：
//选择排序////void select_sort(int a[],int n){ for(int i=0;i
4.堆排序：
基本操作：将待排序序列构造成一个堆，每次将堆首与堆尾交换并把堆的大小减一，并对交换后的堆进行维护。直至堆的大小为1。
最优时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
稳定性：不稳定
代码：
/堆排序///void heap_adjust(int a[],int root,int len) //维护堆{ int ls = root*2+1; int rs = root*2+2; if(ls < len) { int pos = ls; if(rs < len) { if(a[rs] > a[ls]) { pos = rs; } } if(a[root] < a[pos]) { swap(a[root],a[pos]); heap_adjust(a,pos,len); } }}void heap_sort(int a[],int n){ for(int i=n/2; i>=0; i--) heap_adjust(a,i,n); for(int i=n-1; i>0; i--) { swap(a[0],a[i]); heap_adjust(a,0,--n); }}
5.冒泡排序：
基本操作：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
最优时间复杂度：O(n)
最差时间复杂度：O(n^2)
稳定性：稳定
代码：
//冒泡排序///void Bubble_sort(int a[],int n){ for(int i=0;i i;j--) { if(a[j] < a[j-1]) { swap(a[j],a[j-1]); flog = true; } } if(!flog) return; }}
6.快速排序：
基本操作：找到一个基准数，将小于基准数的元素放在基准数的左边，大于基准数的元素放在基准数的右边，此时基准便处于“正确”的位置，接下来对基准数的左、右两部分进行同样的操作。
最优时间复杂度：大多数情况下时间复杂度为O(nlogn)
最差时间复杂度：当待排序序列的所有元素值一样时，时间复杂度为O(n^2)
稳定性：不稳定
代码：
void quick_sort(int a[],int l,int r){ if(l >= r) return; int temp = a[l]; int i = l; int j = r; while(i < j) { while(i temp) j--; if(i < j) a[i++] = a[j]; while(i
7.归并排序：
基本操作：采用分治的策略，并将已经排好序的两个序列通过归并操作，形成一个新的有序序列
最优时间复杂度：O(nlogn)
最差时间复杂度：O(nlogn)
稳定性：稳定
代码：
void Merge(int a[],int l,int mid,int r){ int len1 = mid - l + 1; int len2 = r - mid; int *L = new int[len1]; int *R = new int[len2]; for(int i=0;i = r) return; int mid = (l+r)/2; Merge_sort(a,l,mid); Merge_sort(a,mid+1,r); Merge(a,l,mid,r);}