冒泡排序、快速排序、二分插入排序c++实现

先奉上一段in-place交换的方法

//in-place swap
void swap_int(int& a, int& b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

冒泡排序实现

/*
 * 交换排序之冒泡排序
 * 相邻元素比较大小，将大值交换到后面的位置
 * 优化：不需要与后面已经排好序的元素比较
 *       如果发现一趟比较中没有位置交换，说明排序已经完成
 */
void BubbleSort(int a[], int len)
{
    bool swaped = false;
    for (int i = 0; i < len; ++i)
    {
        for (int j = 1; j < len - i; ++j)
        {
            if (a[j - 1] > a[j])
            {
                swap_int(a[j - 1], a[j]);
                swaped = true;
            }
        }

        if (!swaped) break;
    }
}

快速排序实现

/*
 * 交换排序之快速排序
 * 选用一个值作为比较对象，大值交换到右侧位置，小值交换到左侧位置，递归此操作
 */
void QuickSort(int s[], int left, int right)
{
    if (left < right)
    {
        int i = left, j = right, x = s[left];
        while (i < j)
        {
            while (i < j && s[j] >= x) // 从右向左找第一个小于x的数  
                j--;
            if (i < j)
                s[i++] = s[j];
            print_arr(s, SIZE);
            while (i < j && s[i]< x) // 从左向右找第一个大于等于x的数  
                i++;
            if (i < j)
                s[j--] = s[i];
            print_arr(s, SIZE);
        }
        s[i] = x;
        QuickSort(s, left, i - 1); // 递归调用  
        QuickSort(s, i + 1, right);
    }
}

二分插入排序

/*
 * 插入排序之二分查找法排序
 * 使用二分查找法搜索新元素在已排列好的元素中的插入位置并插入，插入位置后的元素逐个后移
 */
int SearchBinary(int a[], int value, int left_index, int right_index)
{
    if (right_index <= left_index) 
        return a[left_index] < value ? left_index+1:left_index;

    int mid = (right_index + left_index) / 2;
    if (value == a[mid]) 
        return mid + 1;

    if (value > a[mid]) 
        return SearchBinary(a, value, mid + 1, right_index);

    return SearchBinary(a, value, left_index, mid - 1);
}

void InsertSort(int a[], int len)
{
    for (int i = 1; i<len; ++i)
    {
        if (a[i] < a[i - 1])
        {
            int index = SearchBinary(a, a[i], 0, i - 1);
            int tmp = a[i];
            for (int j = i; j>index; --j)
            {
                a[j] = a[j - 1];
            }
            a[index] = tmp;
        }
    }
}