排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序。

常见的排序算法：冒泡、快排、插入、希尔、选择、堆排、归并。

1、冒泡排序

原理：一个无序数组，按照升序排列。int i 代表循环的次数，int j 代表数组的下标，if(arr[j]>arr[j+1]),交换位置，依次类推。每循环一次，一个数字在它相应的位置。

源码：

voidBubble_sort(intarr[],intlen){inti;for(i=0;i<len;i++){intj;for(j=0;j<len-1-i;j++){if(arr[j]>arr[j+1]){inttmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}}}}

时间复杂度o(n^2),空间复杂度o(1).

2、快排：

原理：从中间向两边的探索，在序列中选择一个准基数，用来做参考的数，选择左边的第一个数为例，将序列中所有大于准基数的数放在它的右边，小于的放在它的左边，最终确定准基数的位置。

定义两个变量left、right，可以将其看作指针，指定其对应的某元素，一个指向最左边，一个指向最右边，选择left作为准基数，从最左边的数和它比较，当准基数小于right指向的数时，right--，如果大于right指向的数，arr[left]=arr[right],当准基数大于左边的值时，left++，如果小于左边的值，arr[right]=arr[left],最后将准基数放在其正确的位置，然后重复上述步骤递归。

源码：

voidQuick_sort(intarr[],intFront,intBack){intleft=Front;intright=Back;if(left<right){inttmp=arr[left];while(left<right){while(left<right&&tmp<arr[right]){right--;}arr[left]=arr[right];while(left<right&&tmp>arr[left]){left++;}arr[right]=arr[left];}arr[left]=tmp;Quick_sort(arr,Front,left-1);Quick_sort(arr,left+1,Back);}}

时间复杂度o(nlog2n),空间复杂度o(nlog2n)

3、插入排序：

原理：插入排序就是讲一个数字插入到它本该占据的位置。

源码：

voidInsertsort(intarr[],intlen){inti=0;for(i=0;i<len-1;i++){inttmp=arr[i+1];intpos=i;while(pos>=0&&arr[pos]>tmp){arr[pos+1]=arr[pos];pos--;}arr[pos+1]=tmp;}}

时间复杂度o(n^2),空间复杂度o(1).

4、希尔排序

原理：希尔排序就是基于插入排序的一种改进，先将整个待排元素分成若干个子序列（有相隔某个增量元素组成），分别进行插入排序，然后缩减增量再进行排序，待这整个元素基本有序时（增量足够小），再对全体元素进行一次插入排序。

源码：

voidShellSort(intarr[],intlen){intgap=len;while(gap){gap=gap/2;for(inti=gap;i<len;i++){inttmp=arr[i];intpos=i-gap;while(pos>=0&&arr[pos]>tmp){arr[pos+gap]=arr[pos];pos-=gap;}arr[pos+gap]=tmp;}}}

时间复杂度o(n^2),空间复杂度o(1).

5、选择排序

原理：在待排序列中将第一个元素记为最小的，第一个位置记为最小位置，在剩余所有元素中找到最小的与之交换。

源码：

voidSelectSort(intarr[],intlen){for(inti=0;i<len;i++){intmin=arr[i];intindex=i;for(intj=i+1;j<len;j++){if(arr[j]<min){min=arr[j];index=j;}}arr[index]=arr[i];arr[i]=min;}}

时间复杂度o(n^2),空间复杂度o(1).

6、堆排

将初始化序列构成大堆，此堆为初始的无序区，将堆顶元素与最后一个元素交换位置，得到一个无序区和一个有序区，交换后的堆顶元素不变，因此将堆顶元素向下调整，保证最大堆的性质。

源码：

voidHeapDown(intarr[],inti,intlen){intparent=i;intchild=2*i+1;while(child<len){if(child+1<len&&arr[child]<arr[child+1]){child=child+1;}if(arr[child]>arr[parent]){swap(arr[parent],arr[child]);parent=child;child=parent*2+1;}else{break;}}}voidCreateHeap(intarr[],intlen){inti=0;for(i=len/2-1;i>=0;i--){HeapDown(arr,i,len);}}voidHeapSort(intarr[],intlen){CreateHeap(arr,len);for(inti=len-1;i>=0;i--){swap(arr[0],arr[i]);HeapDown(arr,0,i);}}

时间复杂度o(nlog2n),空间复杂度o(1).

7、归并排序

源码：

voidMergeArray(intarr[],intlow,intmid,inthigh,inta[]){inti=low;intj=mid+1;intk=0;while(i<=mid&&j<=high){if(arr[i]<=arr[j]){a[k]=arr[i];i++;k++;}else{a[k]=arr[j];j++;k++;}}while(i<=mid){a[k]=arr[i];i++;k++;}while(j<=high){a[k]=arr[j];j++;k++;}for(i=0;i<k;i++){arr[low+i]=a[i];}}voidMSort(intarr[],intfirst,intlast,inta[]){if(first<last){intmid=(first+last)/2;MSort(arr,first,mid,a);MSort(arr,mid+1,last,a);MergeArray(arr,first,mid,last,a);}}voidMergesort(intarr[],intsz){int*a=newint[sz];MSort(arr,0,sz-1,a);delete[]a;}

时间复杂度o(nlog2n),空间复杂度o(n)。