选择排序：

算法描述：选择排序思想为先遍历一遍数组，依次将每个数视为校准数，查找到校准数之后的数中最小的数，让它与校准数交换，比如说：49 38 65 76 13 27 52，先将49看为校准数，49后面最小数为13，两者交换：13 38 65 76 49 27 52，依次执行。可以发现一个规律，由于每次校准，都是将相对最小的数放在校准位，所以已经校准过的数，一定的单调不减的！

代码实现：

void SelectSort(int arr[],int n){    //n为数组长度    for (int i=0; i

插入排序：

算法描述：插入排序思想是从第二位开始遍历数组，依次将每个数视为"校准数"，将"校准数"和它前面的一个数进行比较，如果比它前面的数大，则不做任何处理，否则将"被比较的数"后移一位，重复上面操作，校准数再次向前比较，直到找到小于或等于"校准数"的位置，停止比较，将校准数插入正确的位置。例如49 38 65 76 13 27 52，先将38看为校准数，与它的前一位进行比较，38小于49，将49后移一位，变成49 49 65 76 13 27 52,将38插入到第一位，变成38 49 65 76 13 27 52，再将65视为校准数，大于49，不动，接下来76大于65，不动，校准数为13时，依次向前比较，由于前面的数均大于13，则前面的数均会依次后移一位，变成38 38 49 65 76 27 52，再将13插入到第一位变成13 38 49 65 76 27 52，后面的数同理。可以看出每次校准后，校准过的数均为单调不减的！

代码实现：

void InsertSort(int arr[],int n){//n为数组长度    for (int i=1; i
    
     temp; j--) {                arr[j+1]=arr[j];            }//后移            arr[j+1]=temp;//插入到正确位置        }    }}
    

冒泡排序：

算法描述：冒泡排序思想是对相邻两数进行比较和交换，遍历后先把最大的数放在最后面，然后再找次大数，放在倒数第二位，依次进行，遍历结束后整组就都是单调不减的了。例如：49 38 65 76 13 27 52，第一次排序后，38 49 65 13 27 52 76 ，第二次排序后：38 49 13 27 52 65 76， 依次进行···

代码实现：

void BubbleSort(int arr[],int n){//n为数组长度    for (int i=0; i
    
     arr[j+1]) {                int temp=arr[j];                arr[j]=arr[j+1];                arr[j+1]=temp;            }        }    }}
    

如果从某一位开始，后面是有序的，例如1 2 3 4 5 6 7 ，用上面的方法，依然会依次遍历，进行比较，如果发现这种情况，直接终止循环，就能避免造成时间上的浪费。在书上看到一个升级版，利用一个lastExchangeIndex指针，记录上一趟交换中，最后一次交换的位置，如果lastExchangeIndex=1，则代表该次遍历并未进行交换，即数组已经是有序的了。

代码如下：

void BubbleSort(int arr[],int n){//n为数组长度    while (n>1) {//n>1 表明上一趟曾进行记录的交换        int lastExchangeIndex=1;        for (int j=0; j
    
     arr[j+1]) {                int temp=arr[j];                arr[j]=arr[j+1];                arr[j+1]=temp;                lastExchangeIndex=j+1;            }        }        n=lastExchangeIndex;//一趟排序中，无序序列中的最后一个记录所在的位置    }}
    

快速排序：

算法描述：快速排序和冒泡排序有异曲同工之处，基本想法是找一个校准数做枢轴，一趟排序将比枢轴小的数移动到枢轴左侧，比枢轴大的数移到到枢轴右侧，再将枢轴左侧的数和右侧的数各自看成一部分重复上面的操作，如此重复下来，就得到一组有序的数。例如：49 38 65 76 13 27 52，第一次将49作为枢轴，使用两个指针low和high，分别指向数组的开头和结尾，也就是49和52，先让high指针向左扫描，直到high指针指向的数小于枢轴时停止，即指向27时停止，将high指针指向的数（27），赋给low指针，这时数组为：27 38 65 76 13 27 52，这时low指针向右扫描，直到low指针指向的数大于枢轴时停止（65），将low指针指向的数（65），赋给high指针，这时数组为：27 38 65 76 13 65 52 ，依次进行直到low指针与high指针相遇，这时数组为：27 38 13 76 76  65 52，再将枢轴的值赋给两指针所在位置，数组变为：27 38 13 49 76  65 52，即枢轴（49）左侧全部比其小，右侧比它大，再将49左侧和右侧各看成一个整体，进行上述操作，最终可得有序的数组。

代码实现:

int Partition(int arr[],int low ,int high){    int pivokey =arr[low];//记录枢轴位置    while (low
    
     pivokey)            high--;        if (low
    

归并排序：

算法描述：归并排序是利用递归和分而治之思想的一种排序算法。想象一下，如果将数组arr[left...right]分成左右两部分arr[left...mid]和arr[mid+1...right](其中mid=(right+left)  /2)，这时两个子数组又均是有序数组，例如数组1 5 6 2 4 8 分成数组 1 5 6 和数组2 4 8，那么只需要在两数组合并的过程中加入相应判断，就可以得到一个有序数组（----以上对应Merge函数）

那么接下来的任务就是将数组变成相邻两部分有序的子数组，这里采用递归的方法，以mid为中心，将数组划分为左右两部分，再将这两部分各自分成左右两部分,再重复上面操作，直到分无可分，即子数组中只剩下一个元素。由于递归是采用栈的方式实现的，具有后进先出的特点，不防将这个问题反过来看，例如49 38 65 76 13 27 52，先将相邻两元素两两合并：[38 49],[65 76],[13 27],52,再次两两合并[38 49 65 76],[13 27 52],最后再次两两合并可得有序数组。

代码实现：

void Merge(int arr[],int left,int mid,int right){    int temp[right-left+1];    int i=left;    int j=mid+1;    int k=0;    while (i<=mid&&j<=right) {        if (arr[i]<=arr[j]) {            temp[k++]=arr[i++];        }else{            temp[k++]=arr[j++];        }    }    while (i<=mid) {        temp[k++]=arr[i++];    }    while (j<=right) {        temp[k++]=arr[j++];    }    for (int p=0; p
    
     =right) {        return;    }    int mid=(left+right)/2;    Msort(arr, left, mid);    Msort(arr, mid+1, right);    Merge(arr, left, mid, right);}
    

希尔排序：

算法描述：希尔排序是插入排序的优化，设定一个步长（d），将数组里间隔为d的元素分别取出组成一个子数组，例如49 38 65 76 13 27 52，设d=3，那么子数组分别为[49(0） 76(3） 52(6）],[38(1） 13(4）],[65(2） 27(5）],括号内的数字代表下标，每个子数组按照插入算法进行排序，可得[49(0） 52(3） 76(6）],[13(1） 38(4）],[27(2） 65(5）],原数组变成[49 13 27 52 38 65 76],如果这时将步长缩短为2，那么就可以得到相对来说更加有序的数组，最后将步长缩短为1，即可得到有序数组。

代码实现：

void ShellnSert(int arr[],int n,int d){    for (int i=d; i
    
     0&&arr[j]>temp) {            arr[j+d]=arr[j];//如果arr[j]比arr[i]大,arr[j]后移d位            j-=d;        }        if (j!=i-d) {//如果进行过后移            arr[j+d]=temp;//将校准位放到正确位置        }    }}void SSort(int arr[],int n){    int d=n/2;    while (d>=1) {        ShellnSert(arr, n, d);        d/=2;    }}
    

计数排序：

算法描述:计数排序适用于满足一定范围的整数数组，思想是将待排序数组的值作为辅助数组的下标，记录每个值出现的个数，由于辅助数组的下标是自然有序的，那么就可以得到待排序数组中每个值所应该在的位置。例如arr数组[1 5 3 5 4]，先从数组中找到最大值Max=5，由于0~5共6个数，创建辅助数组temp[],长度为6,初始化temp数组使其每位均为零,这时遍历数组，第一位：1 ，则temp[1]++，第二位：5，则temp[5]++,依次下去，最终得到temp=[0 1 0 1 1 2]，由此可见，temp数组的第0位值为0，代表arr数组中没有0，第1位值为1，代表arr数组中有一个1 ，依次下去，第5位值为2，代表arr数组中有2个5，可以发现，由于temp数组下标是自然有序的，我们直接就可以得到arr数组中各个值正确的排序位置，比如说arr数组中的1，由于temp[0]=0（即数字1前面没有任何的数），那么1就是arr数组中的第一个数（即第0位），arr数组中的3，temp[0]+temp[1]+temp[2]=1,那么3前就只有一个数，也就是3在数组中应该排第1位（从0位开始），依次下去，来看5的位置，5有些特殊，因为arr数组中一共出现了两次5，按照上面的方法，两次都排在了第3位，势必会出现问题。不妨将temp修改一下，将temp[i]=temp[i-1]+temp[i],数组temp=[0 1 1 2 3 5],这时temp[i]代表i在arr数组中为第几个数，找到所在位置后temp[i]--，这样即避免了上面的问题，再拿5来举例，遍历到arr[1]=5时，查询到对应temp[5]=5，那么代表5应该为arr数组中的第5个数（即第4位），这时temp[5]--,temp[5]=4,再遍历到arr[3]=5时，查询到对应temp[5]=4，那么代表5应该为arr数组中的第4个数（即第3位），最终得到有序数组。

代码实现：

int MAX(int arr[],int n){    //求数组中的最大值    int max=0;    for (int i=0; i
    
     max?arr[i]:max;    }    return max;}void CountSort(int arr[],int n){    int Max=MAX(arr, n);    int temp[Max+1];    for (int i=0; i