作为志向在科班的有志青年，不能只浮于表面看工程，也得放下身段学基础算法。与年少时就开始沉迷于NOIP的少年们相比，我还得从十分基本的排序算法学起。不过为了给以后的学习铺平道路，辛苦一点学习也在所难免吧！

冒泡排序

作为C课堂上第一个接触到的排序算法，冒泡排序属于比较式排序中最基础的。原理是相邻两个数比较，大的元素后移；经过第一轮排序之后最大的元素位于数组末尾，第二大的元素位于倒数第二位；循环依次进行即可，时间复杂度为$ O(n^2) $。
基本实现（C）：

void BubbleSort(int arr[],int size){
    for (int i = 0; i < size-1; ++i) {
        for (int j = size-1; j > i; --j) {
            if (arr[j-1]>arr[j]){
                int t=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=t;
            }
        }
    }
}

改进1

如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个Flag做标记，默认为0，如果发生交互则置为对应位置，每轮结束时检测Flag，如果为非0则继续，如果为0则返回。

void BubbleSort(int arr[],int size){
    int lastSwap;
    for (int i = 0; i < size-1; ++i) {
        lastSwap = 0;
        for (int j = size-1; j > i; --j) {
            if (arr[j-1]>arr[j]){
                int t=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=t;
                lastSwap = j;
            }
        }
        if(!lastSwap)
            break;
    }
}

改进2

某一轮结束位置为j，但是这一轮的最后一次交换发生在lastSwap的位置，则lastSwap到j之间是排好序的，下一轮的结束点就不必是j--了，而直接到lastSwap即可，代码如下：

void bubble_sort (int a[], int n) {
    int i, j, lastSwap, tmp;
    for (j=n-1; j>0; j=lastSwap) {
        lastSwap=0;     //每一轮要初始化为0，防止某一轮未发生交换，lastSwap保留上一轮的值进入死循环
        for (i=0; i<j; i++) {
            if (a[i] > a[i+1]) {
                tmp=a[i];
                a[i]=a[i+1];
                a[i+1]=tmp;
　　　　　　　　   //最后一次交换位置的坐标
                lastSwap = i;
            }
        }
    }
}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序采用分治法策略将一个序列分为两个。

具体步骤：

• 从数列中挑出一个元素称为基准（pivot），通常以第一个元素为基准。
• 所有小于基准数的元素放在基准数之前，同理大于基准数的元素放在基准数之后。具体的实现方法如图所示：

void quicksort(int arr[],int left,int right){
    int i,j,t,temp;
    if(left>right)
        return;
    temp=arr[left];
    i=left;
    j=right;
    while(i!=j){
        while(arr[j]>=temp and i<j)
            j--;
        while(arr[i]<=temp and i<j)
            i++;
        if(i<j){
            t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
    }
    arr[left]=arr[i];
    arr[i]=temp;
    quicksort(arr,left,i-1);
    quicksort(arr,i+1,right);
}