一、冒泡排序

• 标准版

void popSort(int *p, int n)
{
    for(int i=0; i<n-1; i++)
    {
        for(int j=0; j<n-i-1; j++)
        {
            if(p[j]>p[j+1])
            {
                p[j]^=p[j+1];
                p[j+1]^=p[j];
                p[j]^=p[j+1];
            }
        }
    }
}

• 优化版：序而不排（若有序则不继续排）

void popSort(int *p, int n)
{
    int flag;
    for(int i=0; i<n-1; i++)
    {
        flag = 1;
        for(int j=0; j<n-i-1; j++)
        {
            if(p[j]>p[j+1])
            {
                p[j]^=p[j+1];
                p[j+1]^=p[j];
                p[j]^=p[j+1];
                flag = 0;
            }
        }
        if(flag)
            break;
    }
}

二、插入排序

• 标准版（第一个元素天然有序）

void insertSort(int *arr, int n)
{
    int t,i,j;
    for(i=1; i<n; i++)
    {
        t = arr[i];
        for(j=i; j-1>=0 && t<arr[j-1]; j--)
        {
            arr[j] = arr[j-1];
        }
        arr[j] = t;
    }
}

• 优化版 希尔排序 分组以减少趟数

void shellSort(int *arr, int n)
{
    int t,i,j;
    int gap = n/2;
    while(gap>=1)
    {
        for(i=gap; i<n; i++)
        {
            t = arr[i];
            for(j=i; j-gap>=0 && t<arr[j-gap]; j = j-gap)
            {
                arr[j] = arr[j-gap];
            }
            arr[j] = t;
        }
        gap = gap/2;
    }
}

三、选择排序

• 标准版

void selectSort(int * arr, int n)
{
    for(int i=0; i<n-1; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(arr[i]>arr[j])
            {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }
        }
    }
}

• 优化版（记录下标，比而不换）

void selectSort(int * arr, int n)
{
    int idx;
    for(int i=0; i<n-1; i++)
    {
        idx = i;
        for(int j=i+1; j<n; j++)
        {
            if(arr[idx]>arr[j])
            {
                idx = j;
            }
        }
        if(idx != i)
        {
            arr[i]  ^= arr[idx];
            arr[idx]^= arr[i];
            arr[i]  ^= arr[idx];
        }
    }
}

四、快速排序

• 递归实现

void quickSort(int *arr, int left, int right)
{
    if(left < right)
    {
        int pivot = arr[left], l = left, h = right;
        while(l < h)
        {
            while(l<h && arr[h]>=pivot)  //大而移动，小而赋值
                h--;
            arr[l] = arr[h];

            while(l<h && arr[l]<=pivot)  //小而移动，大而赋值
                l++;
            arr[h] = arr[l];
        }
        arr[h] = pivot;

        quickSort(arr,left,h-1);
        quickSort(arr,h+1,right);
    }
}

五、归并排序

• 将两个有序数组合并，使其仍然有序

void mergeArr(int *src, int *tmp, int start, int mid, int end)
{
    int i = start; int j = mid+1; int k = start;
    while(i != mid+1 && j != end+1)
    {
        if(src[i] < src[j])
            tmp[k++] = src[i++];
        else
            tmp[k++] = src[j++];
    }
    if(i == mid+1)
        while(j != end+1)
            tmp[k++] = src[j++];
    else
        while(i != mid+1)
            tmp[k++] = src[i++];

    while(start <= end)
    {
        src[start] = tmp[start];
        start++;
    }
}

void mergeSort(int *arr, int *tmp,int start, int end)
{
    if(start<end)
    {
        int mid = (start + end)/2;
        mergeSort(arr,tmp,start,mid);
        mergeSort(arr,tmp,mid+1,end);
        mergeArr(arr,tmp,start,mid,end);
    }
}

六、二分查找

• 标准版

int binSearch(int *arr, int low, int high, int find)
{
    int mid;
    while(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == find)
            return mid;
        else if(arr[mid] < find)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;
}

• 递归版

int binSearch(int *arr, int low, int high, int find)
{
    int mid;
    if(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == find)
            return mid;
        else if(arr[mid] < find)
            return binSearch(arr,mid+1,high,find);
        else
            return binSearch(arr,low,mid-1,find);
    }
    return -1;
}