前言：

排序算法是面试经常考的题，游戏开发对算法是非常看重的，不说你了解所有算法，但是基本的排序算法是必须掌握的基本功，除了排序外查找也是很必要掌握的基本功。

---

零、概览图

指标对比：

一、冒泡排序

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;
            }
        }
    }
}

二、选择排序

void selection_sort (int a[], int n) {
    int i,j,pos,tmp;
    for (i=0; i<n-1; i++) {
　　　　  //寻找最小值的下标
        for (pos=i, j=i+1; j<n; j++)
            if (a[pos]>a[j])
                pos=j;
        if (pos != i) {
            tmp=a[i];
            a[i]=a[pos];
            a[pos]=tmp;
        }
    }
}

三、插入排序

void insertion_sort (int a[], int n) {
    int i,j,v;
    for (i=1; i<n; i++) {
　　　　  //如果第i个元素小于第j个，则第j个向后移动
        for (v=a[i], j=i-1; j>=0&&v<a[j]; j--)
            a[j+1]=a[j];
        a[j+1]=v;
    }
}

四、希尔排序

void shell_sort(int a[], int n)
{
    int d, i, j, temp; //d为增量
    for(d = n/2;d >= 1;d = d/2) //增量递减到1使完成排序
    {
        for(i = d; i < n;i++)   //插入排序的一轮
        {
            temp = a[i];
            for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
            {
                a[j + d] = a[j];
            }
        a[j + d] = temp;
        }
    }
}

五、归并排序

void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void merge_sort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        merge_sort(a, first, mid, temp);    //左边有序
        merge_sort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

六、快速排序

  public static void quickSort(int[] arr, int left, int right)
    {
        if (left < right) {
            int mark = arr[left];
            int i = left;
            int j = right;
            while (i < j) {
                // 从后向前查找
                while (j > i && arr[j] >= mark) {
                    j--;
                }
                if (j > i) {
                    arr[i++] = arr[j];
                }
                // 从前向后查找
                while (i < j && arr[i] < mark) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = mark;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }

七、堆排序

void heapAdjust(int a[], int i, int nLength)
{
    int nChild;
    int nTemp;
    for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild)
    {
        // 子结点的位置=2*（父结点位置）+ 1
        nChild = 2 * i + 1;
        // 得到子结点中较大的结点
        if ( nChild < nLength-1 && a[nChild + 1] > a[nChild])
            ++nChild;
        // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
        if (nTemp < a[nChild])
        {
            a[i] = a[nChild];
            a[nChild]= nTemp;
        }
        else
        // 否则退出循环
            break;
    }
}

// 堆排序算法
void heap_sort(int a[],int length)
{
    int tmp;
    // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    //length/2-1是第一个非叶节点，此处"/"为整除
    for (int i = length / 2 - 1; i >= 0; --i)
        heapAdjust(a, i, length);
    // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for (int i = length - 1; i > 0; --i)
    {
        // 把第一个元素和当前的最后一个元素交换，
        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
      ///  Swap(&a[0], &a[i]);
          tmp = a[i];
          a[i] = a[0];
          a[0] = tmp;
        // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        heapAdjust(a, 0, i);
    }
}