排序¶

存储结构-记录序列以顺序表存储¶

#define MAXSIZE 20 //设记录不超过20个

typedef int KeyType; //设关键字为整型量(int型)
typedef int InfoType;

typedef struct { //定义每个记录（数据元素）的结构
    KeyType key; //关键字
    InfoType otherinfo; //其他数据项
}RedType; //Record Type

typedef struct { //定义顺序表的结构
    RedType r[MAXSIZE + 1]; //存储顺序表的向量
                            //r[0]一般作哨兵或缓冲区
    int length; //顺序表的长度
}SqList;

1-插入排序¶

直接插入排序¶

void InsertSort(SqList &L)
{
    for (int i = 2; i <= L.length; i++) { 
        L.elem[0] = L.elem[i]; //复制为哨兵
        int j = i - 1;
        for (; L.elem[0].key < L.elem[j].key; j--) { //若"<""，需将L.elem[i]插入有序字表
            L.elem[j + 1] = L.elem[j]; //记录后移
        }
        L.elem[j + 1] = L.elem[0]; //插入到正确位置
    }
    //算法时间复杂度：O(n^2)，空间复杂度：O(1)
}

//插入排序
void insertion_sort(vector<int>& nums, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j) {
            swap(nums[j], nums[j - 1]);
        }
    }
}

折半插入排序¶

void BInsertSort(SqList& L)
{
    for (int i = 2; i < L.length; ++i) //依次插入第2~第n个元素
    {
        L.elem[0] = L.elem[i]; //哨兵位
        int low = 1, high = i - 1; //采用二分查找法查找插入位置
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (L.elem[0].key < L.elem[mid].key)
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            } //循环结束，high+1则为插入位置
        //这个排序的根本思想，是将折半排序的比较区间，逐渐缩小到最大的小于等于哨兵元素的那个元素的位置
        //然后这个位置再加1，就是此元素应该插入的位置
        for (int j = i; j >= high + 1; --j)
        {
            L.elem[j + 1] = L.elem[j]; //移动元素
        }
        L.elem[high + 1] = L.elem[0]; //插入到正确位置
    }
}

2-交换排序¶

冒泡排序¶

void BubbleSort(SqList& L) {
    int flag = 1; //flag作为是否交换的标记
    RedType temp; //交换时临时存储
    for (int i = 1; i <= L.length - 1 && flag==1; i++) { //总共需要（L.length-1）趟
        flag = 0;
        for (int j = 1; j <= L.length - i; j++){ //第i趟需要比较（L.length-1-i）次
            if (L.elem[j].key > L.elem[j + 1].key) { //发生逆序
                flag = 1; //发生交换，flag置为1，若本趟没发生交换，flag保持为0
                temp = L.elem[j]; 
                L.elem[j] = L.elem[j + 1]; 
                L.elem[j + 1] = temp; //交换
            }
        }
    }
}

//冒泡排序
void bubble_sort(vector<int>& nums, int n) {
    bool swapped;
    for (int i = 1; i < n; ++i) {
        swapped = false;
        for (int j = 1; j < n - i + 1; ++j) {
            if (nums[j] < nums[j - 1]) {
                swap(nums[j], nums[j - 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

快速排序¶

int Partition(SqList &L, int low, int high)
{
    //设置哨兵位
    L.elem[0] = L.elem[low];
    //设置中心元素
    int pivotkey = L.elem[0].key;
    //循环排序开始
    while (low < high)
    {
        //从表尾开始找元素
        while (low < high && L.elem[high].key >= pivotkey)
            --high; //向前移动high
        //跳出上面这个循环了，意味着要么low==high了，要么在表尾找到了一个小于中心元素的元素
        L.elem[low] = L.elem[high];
        //从表头开始找元素
        while (low < high && L.elem[low].key < pivotkey)
            ++low; //向后移动low
        //跳出上面这个循环了，意味着要么low==high了，要么在表尾找到了一个大于中心元素的元素
        L.elem[high] = L.elem[low];
    } //表头low和表尾high相等时，退出循环 
    L.elem[low] = L.elem[0]; //此时low和high相同，付给谁都一样
    //返回排序后中心元素的位置
    return low; //low其实是等于high，返回low或者返回high是一个道理
}
void QSort(SqList& L, int low, int high) //对顺序表L快速排序
{
    //好像二叉树的先序遍历啊
    if (low < high) //长度大于1
    {
        //将L.elem[low...high]一分为二，privotloc为数轴元素排好序的位置
        int pivotloc = Partition(L, low, high); 
        //再对序列的左半部分进行排序找中心位置
        QSort(L, low, pivotloc - 1);
        //再对序列的右半部分进行排序找中心位置
        QSort(L, pivotloc + 1, high);
    }
}

//快速排序
//左闭右开
void quick_sort(vector<int>& nums, int l, int r) {
    //如果数组大小为1，则无需排序
    if (l + 1 >= r) {
        return;
    }
    //因为传入的是nums.size()所以要减1
    int first = l, last = r - 1, key = nums[first];
    //确定中心点位置为first
    while (first < last) {
        while (first < last && nums[last] >= key) {
            --last;
        }
        //从后往前，找到比key值小的数，搬到first的位置
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) {
            ++first;
        }
        //从前往后，找到比key值大的数，搬到刚才空出来的last的位置
        nums[last] = nums[first];
    }
    //把key值赋给first位，此时的first=last
    nums[first] = key;
    //对低子表递归排序
    quick_sort(nums, l, first);
    //对高子表递归排序
    quick_sort(nums, first + 1, r);
}

3-选择排序¶

简单选择排序算法¶

void SelectSort(SqList& L) {
    RedType temp; //交换时临时存储
    for (int i = 1; i < L.length; i++) {
        int k = i;
        for (int j = i + 1; j <= L.length; j++) {
            if (L.elem[j].key < L.elem[k].key) {
                k = j; //记录最小值位置
            }
        }
        if (k != i) {
            temp = L.elem[k];
            L.elem[k] = L.elem[i];
            L.elem[k] = temp; //交换
        }
    }
}

//选择排序 
void selection_sort(vector<int>& nums, int n) {
    int mid;
    for (int i = 0; i < n - 1; ++i) {
        mid = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[mid]) {
                mid = j;
            }
        }
        swap(nums[mid], nums[i]);
    }
}

4-归并排序¶

//归并排序
void merge_sort(vector<int>& nums, int l, int r, vector<int>& temp) {
    if (l + 1 >= r) {
        return;
    }
    // divide
    int m = l + (r - l) / 2;
    merge_sort(nums, l, m, temp);
    merge_sort(nums, m, r, temp);
    // conquer
    int p = l, q = m, i = l;

    //将两个有序序列合并成一个有序序列
    while (p < m || q < r) {
        if (q >= r || (p < m && nums[p] <= nums[q])) {
            temp[i++] = nums[p++];
        }
        else {
            temp[i++] = nums[q++];
        }
    }
    for (i = l; i < r; ++i) {
        nums[i] = temp[i];
    }
}