排序算法

冒泡排序

从要排序序列的第一个元素开始，不断比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。

每找到待排序序列的最大值时，就将该最大值固定在待排序序列的尾部，且每找到一个待排序序列最大值需要循环一次，n 个值则需要循环 n 次，但最后一个值无需比较，则实际需循环 n-1 次，即 i < arr.length - 1 。

void bubbleSort (int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

当然，该方法还可以进行优化。

定义一个布尔变量 flag，用来标记每轮是否进行了交换。在每轮遍历开始时，将 flag 设置为 false。若当轮没有发生交换，即此时 flag 依然为 false，说明此时数组已经按照升序排列。此时外层循环直接退出，排序结束。

void bubbleSort (int arr[]) {
    boolean flag = false;
    for (int i = 0; i < arr.length - 1; i++) {
        flag = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true; //该轮发生交换
            }
        }
        if (!flag) {
            break; //数组已有序
        }
    }
}

复杂度分析：

• 时间复杂度 O(n^2)

• 空间复杂度 O(1)

选择排序

选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。同样，选择排序也需要比较 n - 1轮，最后一轮无需比较。

void selectSort (int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i; //初始化最小值索引
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

复杂度分析：

• 时间复杂度 O(n^2)

• 空间复杂度 O(1)

直接插入排序

• 数据类型定义

typedef int ElemType;

typedef struct
{
    ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
    int length;     //顺序表长度
} SqList;

• 算法实现

/**
 * 直接插入排序
 */
void insertSort(SqList &L)
{
    int i, j;
    for (i = 2; i <= L.length; i++)
    {
        if (L.elem[i] < L.elem[i - 1])
        {
            //将L.elem[i]保存在空闲的0号单元，并作为哨兵
            L.elem[0] = L.elem[i];
            L.elem[i] = L.elem[i - 1];
            //因为有哨兵L.elem[0]，所以条件 j>0 可写可不写
            for (j = i - 2; L.elem[0] < L.elem[j]; j--)
            {
                L.elem[j + 1] = L.elem[j]; //记录后移
            }
            L.elem[j + 1] = L.elem[0]; //插入到正确位置
        }
    }
}

希尔排序

• 数据类型定义

typedef int ElemType;

typedef struct
{
    ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
    int length;     //顺序表长度
} SqList;

• 算法实现

/**
 * 一趟希尔插入排序
 */
void shellInsert(SqList &L, int dk)
{
    int i, j;
    for (i = dk + 1; i <= L.length; i++)
    {
        if (L.elem[i] < L.elem[i - dk])
        {
            L.elem[0] = L.elem[i];
            //条件j>0不能省，因为插入的步长为dk，L.elem[0]无法再充当哨兵
            for (j = i - dk; j > 0 && L.elem[0] < L.elem[j]; j -= dk)
            {
                L.elem[j + dk] = L.elem[j]; //记录后移
            }
            L.elem[j + dk] = L.elem[0]; //插入到正确位置
        }
    }
}

/**
 * 希尔排序
 */
void shellSort(SqList &L, int dlta[], int t)
{
    int k;
    //按增量dlta[0..t-1]对顺序表L进行希尔插入排序
    for (k = 0; k < t; k++)
    {
        shellInsert(L, dlta[k]);
    }
}

快速排序

• 算法实现（版本一）

/**
 * 划分算法
 */
int Partition(int rcd[], int low, int high)
{
    int pivot = rcd[low];    //记录枢纽关键字
    while (low < high)      //从 low 和 high 两端交替向中间移动
    { 
        while (low < high && rcd[high] >= pivot)
            high--;
        rcd[low] = rcd[high];   //比枢纽关键字小的关键字移到低端
        while (low < high && rcd[low] <= pivot)
            low++;
        rcd[high] = rcd[low];   //比枢纽关键字大的关键字移到高端
    }
    rcd[low] = pivot;       //枢纽移到正确位置
    return low;             //返回枢纽位置
}

/**
 * 快速排序（版本一） 
 */
void QuickSort(int rcd[], int low, int high)
{
    int pivotloc; //枢纽位序
    if (low < high)
    {
        pivotloc = Partition(rcd, low, high);
        QuickSort(rcd, low, pivotloc - 1);  //对枢纽之前的子序列递归快排
        QuickSort(rcd, pivotloc + 1, high); //对枢纽之后的子序列递归快排
    }
}

• 算法实现（版本二）

/**
 * 快速排序（版本二） 
 */
void quick_sort(int rcd[], int low, int high){
    if(low >= high){    //递归结束条件
        return;
    }
    int pivot = rcd[low]; 
    int left = low;
    int right = high;
    while (low < high){
        while (low < high && rcd[high] >= pivot)
            high--;
        rcd[low] = rcd[high];
        while (low < high && rcd[low] <= pivot)
            low++;
        rcd[high] = rcd[low];
    }
    rcd[low] = pivot;
    quick_sort(rcd, left, low-1);   //对枢纽之前的子序列递归快排
    quick_sort(rcd, high+1, right); //对枢纽之后的子序列递归快排
}

归并排序

• 算法实现（版本一）

/**
 * 2-路归并 
 */
void Merge(int SR[], int TR[], int i, int m, int n){
    //将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
    int k, j;
    for (k = i, j = m + 1; i <= m && j <= n; k++){
        //将SR中关键字从小到大复制到TR中
        if (SR[i] <= SR[j]){
            TR[k] = SR[i++];
        }else{
            TR[k] = SR[j++];
        }
    }
    while (i <= m)          //将剩余的SR[i..m]复制到TR
        TR[k++] = SR[i++];
    while(j <= n)           //将剩余的SR[j..n]复制到TR
        TR[k++] = SR[j++];
}

/**
 * 归并排序（版本一） 
 */
void MergeSort(int R1[], int R2[], int i, int low, int high){
    //对R1[s..t]归并排序，若i%2==1，则排序后的记录存入R2[s..t]，否则存入R1[s..t]
    int mid;
    if(low == high){                //结束拆分，准备归并
        if(i%2 == 1){
            R2[low] = R1[low];      //为保证最后一趟归并到 R1 数组
        }
    }else{
        mid = (low + high) / 2;     //将区间[s..t]平分为[s..mid]和[mid..t]
        MergeSort(R1, R2, i+1, low, mid);       //对区间[s..mid]递归
        MergeSort(R1, R2, i+1, mid+1, high);    //对区间[mid..t]递归
        if(i%2 == 1){
            Merge(R1, R2, low, mid, high);      //将R1[s..mid]和R1[mid+1..t]归并到R2[s..t]
        }else{
            Merge(R2, R1, low, mid, high);      //将R2[s..mid]和R2[mid+1..t]归并到R1[s..t]
        }
    }
}

• 算法实现（版本二）

/**
 * 归并排序（版本二）
 */
void merge_sort(int SR[], int TR[], int low, int high){
    int i, j, k;
    if(low >= high){    //直到有序（即只剩一个数）
        return;
    }
    int mid = (low + high) / 2;
    merge_sort(SR, TR, low, mid);
    merge_sort(SR, TR, mid+1, high);
    //将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
    for(k=low, i=low, j=mid+1; i<=mid && j<=high; k++){
        if(SR[i] <= SR[j]){
            TR[k] = SR[i++];
        }else{
            TR[k] = SR[j++];
        }
    }   
    while(i <= mid)
        TR[k++] = SR[i++];
    while(j <= high)
        TR[k++] = SR[j++];
    for(k=low; k<=high; k++){
        SR[k] = TR[k];      //复制回待排数组
    } 
}

查找算法

折半查找

• 算法实现（递归版）

int BinSearch(int rcd[], int key, int low, int high){
    //在有序序列rcd[low..high]中折半查找目标关键字key
    int mid = (low + high) / 2;
    if(low > high)          
        return -1;          //找不到key，返回-1
    if(rcd[mid] == key)     
        return mid;         //中间关键字与目标关键字匹配，返回中间关键字下标
    else if(rcd[mid] > key) 
        return BinSearch(rcd, key, low, mid-1);     //在前半区折半查找
    else                    
        return BinSearch(rcd, key, mid+1, high);    //在后半区折半查找
}

• 算法实现（非递归版）

int bin_search(int rcd[], int key, int low, int high){
    //在有序序列rcd[low..high]中折半查找目标关键字key
    int mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(rcd[mid] == key)
            return mid;
        else if(rcd[mid] > key)
            high = mid - 1;     //在前半区折半查找
        else
            low = mid + 1;      //在后半区折半查找
    }
    return -1;      //找不到key，返回-1
}