数据结构之排序

快来打我* 2022-08-21 14:51 97阅读 0赞

1、这篇文章中，涉及到的排序算法有：冒泡、选择、堆排序、快排。

2、算法原理概述

/// --------------       冒泡排序         ----------------
    /* 冒泡排序
     
     算法原理：
     1、比较相邻的两个元素，若第一个比第二个大，就交换他们两个
     2、从第一个到结尾的最后一对，对每一对相邻元素做同样的操作。最后的元素应该是最大的数
     3、除了最后一个，针对所有的元素重复以上的步骤
     4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
     5、注意：冒泡排序，默认每次都是找的最大或者最小的值，每一轮比较完毕，最后的元素一定是最大或最小的值
     */
    
    /// 帧数或浮点数皆可使用
    template <typename T>
    void bubble_sort(T *array, int length)
    {
        /// 计数器
        int i = 0, j =0;
        
        ///
        for (; i < length - 1; i++)
        {
            for (j = 0; j < length - 1 - i; j++)
            {
                if (array[j] > array[j+1])
                {
                    array[j+1] = array[j] ^ array[j+1];
                    array[j] = array[j] ^ array[j+1];
                    array[j+1] = array[j] ^ array[j+1];
                }
            }
        }
    }
    /// --------------       冒泡排序         ----------------
    
    
    /// --------------       选择排序         ----------------
    /*
        原理：每一次从待排序的数据元素中选择出最小的或者最大的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
        选择排序的第一层循环从开始元素到倒数第二个元素，主要是在每次进入第二层的循环之前，将外层循环下的值给临时变量，接下来的第二层循环中若发现比这个最小的位置的元素更小的元素，则将更小的下表赋给临时变量，最后，在二层循环退出后，若临时变量没有改变，则说明没有改变，有比当前外层循环更小的元素，需要将这两个元素交换
     */
    template<typename T>
    void selection_sort(T *array, int length)
    {
        /// 计数器
        int temp = NULL;
        T array_temp;
        
        for (int i= 0; i < length - 1; i++)
        {
            /// 记录位置
            temp = i;
            for (int j = i + 1; j < length; j++)
            {
                if (array[temp] > array[j])
                {
                    /// 记录大的值得位置
                    temp = j;
                }
            }
            /// 这里是二层循环结束的地方
            if (i != temp)
            {
                array_temp = array[temp];
                array[temp] = array[i];
                array[i] = array_temp;
            }
        }
        
    }
    /// --------------       选择排序         ----------------
    
    /// --------------       堆排序           ----------------
    /*      思想  和 基本操作
     
     (1）用大根堆排序的基本思想
     ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
     ② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
     ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
     
     (2)大根堆排序算法的基本操作：
     ①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。
     ②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
     ③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)
     */
    ///--------整理结点
    template<typename T>
    void MinHeapify(T *array, int size, int element)
    {
        /// 左右子树
        int lchild = element * 2 + 1;
        int rchild = lchild + 1;
        
        /// 子树均在范围内
        while (rchild < size)
        {
            /// 若左右子树都小
            if (array[element] < array[lchild] && array[element] < array[rchild])
            {
                return;
            }
            /// 若左边最小
            if (array[lchild] < array[rchild])
            {
                /// 把左面的提到上面去
                swap(array[element], array[rchild]);
                /// 循环时，整理子树
                element = lchild;
            }
            /// 否则右边最小，同理
            else
            {
                swap(array[element], array[rchild]);
                element = lchild;
            }
            /// 重新计算子树的位置
            lchild = element * 2 + 1;
            /// 只有左子树且子树小于自己
            if (lchild < size && array[lchild] < array[element])
            {
                swap(array[lchild], array[element]);
            }
            return;
        }
    }
    
    /// ----- 堆排序操作
    template<typename T>
    void Heap_sort(T *array, int size)
    {
        /// 从子树整理树
        for (int i = size - 1; i >= 0; i--)
        {
            MinHeapify(array, size, i);
        }
        /// 拆除树
        while (size > 0)
        {
            /// 将根与数组最末交换
            swap(array[size-1], array[0]);
            /// 树大小减一
            size--;
            /// 整理树
            MinHeapify(array, size, 0);
        }
        return;
    }
    
    /// --------------       堆排序           ----------------
    
    
    /// --------------       快速排序         ----------------
    /*
        基本思想
        通过第一趟排序，将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分小，然后再对这2部分数据进行排序整个过程可以地柜进行。
        基本介绍
        首先任意选取一个数据，通常选择第一个元素作为关键数据，然后将所有比它小的数据都放到它的前面，所有比它大的数据都放到它后面。
     
        一趟快速排序的算法是：
        1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
        2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
        3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key   的值A[j]，将A[j]和A[i]互换；
        4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
        5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
     
     
     快排的一个循环 
        从最后找比关键值小的。
        从前找比关键之大的。
        合在一起为一个循环。
     */
    template<typename T>
    void Quick_sort(T array[], int low, int high)
    {
        if (low >= high)
        {
            return ;
        }
        int first = low;
        int last = high;
        /// 用第一个元素作为关键值
        int key = array[first];
        
        /// 一个循环= 从后向前 + 从前向后
        while (first < last)
        {
            /// 从最后开始找比关键值大的元素，找到并交换到关键值得位置
            while (first < last && array[last] >= key)
            {
                --last;
            }
            /// 将比第一个小的移动到低端
            array[first] = array[last];
            
            while (first < last && array[first] <= key)
            {
                ++first;
            }
            /// 将比第一个大的移动到高端
            array[last] = array[first];
        }
        
        /// 记录关键值
        array[first] = key;
        /// 递归调用
        Quick_sort(array, low, high);
        Quick_sort(array, first + 1, high);
    }
    /// --------------       快速排序         ----------------
    
    /// --------------       归并排序         ----------------
    
    /*
        算法概述
        该算法是分治法的一个非常典型的应用。
        算法过程：
        比较a[i]与a[j]的大小，若a[i]<= a[j]，则将第一个表中的元素a[i]复制到r[k]中，令i和K分别加上1；
    否则，将第二个有序表中的元素a[j]复制到r[k]中，并令k和j分别+1，如此循环下去。归并算法常采用递归实现。
        
        归并操作示例
     归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
     如　设有数列{6，202，100，301，38，8，1}
     初始状态：6,202,100,301,38,8，1
     第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
     第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
     第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
     总的比较次数为：3+4+4=11,；
     逆序数为14；
     
     */
    template<typename T>
    void Merege(T *sourceArray, T *aimArray, int startIndex, int midIndex, int endIndex)
    {
        int i = startIndex;
        int j = midIndex + 1;
        int k = endIndex;
        
        
        while (i != midIndex && j != midIndex)
        {
            if (sourceArray[i] >= sourceArray[j])
            {
                aimArray[k++] = sourceArray[i++];
            }
            else
            {
                aimArray[k++] = sourceArray[j++];
            }
        }
        
        /// 把剩下的全部合并到新数组中
        while (i != midIndex)
        {
            aimArray[k++] = sourceArray[i++];
        }
        while (j != midIndex)
        {
            aimArray[k++] = sourceArray[j++];
        }
        
        /// 重新归并数组
        for (i = startIndex; i <= endIndex; i++)
        {
            sourceArray[i] = aimArray[i];
        }
    }
    
    template<typename T>
    /// 内部使用递归
    void Merege_sort(T *sourceArr, T *aimArr, int startIndex, int endIndex)
    {
        int midIndex = NULL;
        if(startIndex < endIndex)
        {
            midIndex = (startIndex + endIndex) / 2;
            Merege_sort(sourceArr, aimArr, startIndex, midIndex);
            Merege_sort(sourceArr, aimArr, midIndex+1, endIndex);
            Merege(sourceArr, aimArr, startIndex, midIndex, endIndex);
        }
    }
    
    
    /// --------------       归并排序         ----------------

3、示例代码（C++实现）

注意：导入头文件有：

#include <iostream>
    #include <stdlib.h>

使用命名空间std;

using namespace std;

//------------------------- 我是分割线 -----------------------

A 冒泡排序

void m_Bubble_sort(int *array, int length)
    {
        for (int i = 0; i < length - 1; i++)
        {
            for (int j = 0; j < length - 1 - i; j++)
            {
                if (array[j] > array[j+1])
                {
                    array[j] = array[j] ^ array[j+1];
                    array[j+1] = array[j] ^ array[j+1];
                    array[j] = array[j] ^ array[j+1];
                }
            }
        }
    }

B、选择排序

/// 选择排序
    void m_Selectiont_sort(int *array, int length)
    {
        int index = NULL;
        
        for (int i = 0; i < length - 1; i++)
        {
            /// 记录位置
            index = i;
            for (int j = i + 1; j < length; j++)
            {
                /// 判断索引的值是否变化
                if (array[index] > array[j])
                {
                    index = j;
                }
            }
            /// 若不相等，则交换数
            if (index != i)
            {
                array[index] = array[index] ^ array[i];
                array[i] = array[index] ^ array[i];
                array[index] = array[index] ^ array[i];
            }
        }
    }

C、快排

/// 快速排序, 小的数移动到低端，大的数移动到高端
    void m_Quick_sort(int *array, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        /// 定义关键字
        int key = array[first];
        
        while (first < last)
        {
            /// 首先进行的是倒序查找
            while (last > first && array[last] >= key)
            {
                --last;
            }
            array[first] = array[last];
            /// 接着为正序查找
            while (last > first && array[first] <= key)
            {
                ++first;
            }
            ///将第一个大的移动到高端
            array[last] = array[first];
        }
        
        /// 记录枢轴关键字,放到高端
        array[first] = key;
        /// 递归调用
        m_Quick_sort(array, low, first - 1);
        m_Quick_sort(array, first + 1, high);
    }

D、输出数组内容函数原型

/// 数组输出函数
    void showArray(int *array, int length)
    {
        for (int i = 0; i < length; i++)
        {
            cout << array[i] << " ";
        }
        cout << endl;
    }

E、 main函数调用示例

///主函数
    int main(int argc, const char * argv[])
    {
        /// 排序测试数组
        int array[8] = {4, 3, 2, 1, 0, -1, -2, -3};
        
        cout << "原数组内容" << endl;
        for (int i = 0; i < 8; i++)
        {
            cout << array[i] << " ";
        }
        cout << endl;
        
        /// 调用快排
        m_Quick_sort(array, 0, 7);
        
        
        cout << "排序结果" << endl;
        showArray(array, 8);
    
        return 0;
    }

F、调用输出结果：

![Center][]

4、代码汇总

下面的代码，包括我学习排序和复习排序的代码汇总。笔记汇总。

#include <iostream>
    #include <stdlib.h>
    #include <bitset>
    using namespace std;
    
    /// --------------       冒泡排序         ----------------
    /* 冒泡排序
     
     算法原理：
     1、比较相邻的两个元素，若第一个比第二个大，就交换他们两个
     2、从第一个到结尾的最后一对，对每一对相邻元素做同样的操作。最后的元素应该是最大的数
     3、除了最后一个，针对所有的元素重复以上的步骤
     4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
     5、注意：冒泡排序，默认每次都是找的最大或者最小的值，每一轮比较完毕，最后的元素一定是最大或最小的值
     */
    
    /// 帧数或浮点数皆可使用
    template <typename T>
    void bubble_sort(T *array, int length)
    {
        /// 计数器
        int i = 0, j =0;
        
        ///
        for (; i < length - 1; i++)
        {
            for (j = 0; j < length - 1 - i; j++)
            {
                if (array[j] > array[j+1])
                {
                    array[j+1] = array[j] ^ array[j+1];
                    array[j] = array[j] ^ array[j+1];
                    array[j+1] = array[j] ^ array[j+1];
                }
            }
        }
    }
    /// --------------       冒泡排序         ----------------
    
    
    /// --------------       选择排序         ----------------
    /*
        原理：每一次从待排序的数据元素中选择出最小的或者最大的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
        选择排序的第一层循环从开始元素到倒数第二个元素，主要是在每次进入第二层的循环之前，将外层循环下的值给临时变量，接下来的第二层循环中若发现比这个最小的位置的元素更小的元素，则将更小的下表赋给临时变量，最后，在二层循环退出后，若临时变量没有改变，则说明没有改变，有比当前外层循环更小的元素，需要将这两个元素交换
     */
    template<typename T>
    void selection_sort(T *array, int length)
    {
        /// 计数器
        int temp = NULL;
        T array_temp;
        
        for (int i= 0; i < length - 1; i++)
        {
            /// 记录位置
            temp = i;
            for (int j = i + 1; j < length; j++)
            {
                if (array[temp] > array[j])
                {
                    /// 记录大的值得位置
                    temp = j;
                }
            }
            /// 这里是二层循环结束的地方
            if (i != temp)
            {
                array_temp = array[temp];
                array[temp] = array[i];
                array[i] = array_temp;
            }
        }
        
    }
    /// --------------       选择排序         ----------------
    
    /// --------------       堆排序           ----------------
    /*      思想  和 基本操作
     
     (1）用大根堆排序的基本思想
     ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
     ② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
     ③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
     
     (2)大根堆排序算法的基本操作：
     ①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。
     ②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
     ③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)
     */
    ///--------整理结点
    template<typename T>
    void MinHeapify(T *array, int size, int element)
    {
        /// 左右子树
        int lchild = element * 2 + 1;
        int rchild = lchild + 1;
        
        /// 子树均在范围内
        while (rchild < size)
        {
            /// 若左右子树都小
            if (array[element] < array[lchild] && array[element] < array[rchild])
            {
                return;
            }
            /// 若左边最小
            if (array[lchild] < array[rchild])
            {
                /// 把左面的提到上面去
                swap(array[element], array[rchild]);
                /// 循环时，整理子树
                element = lchild;
            }
            /// 否则右边最小，同理
            else
            {
                swap(array[element], array[rchild]);
                element = lchild;
            }
            /// 重新计算子树的位置
            lchild = element * 2 + 1;
            /// 只有左子树且子树小于自己
            if (lchild < size && array[lchild] < array[element])
            {
                swap(array[lchild], array[element]);
            }
            return;
        }
    }
    
    /// ----- 堆排序操作
    template<typename T>
    void Heap_sort(T *array, int size)
    {
        /// 从子树整理树
        for (int i = size - 1; i >= 0; i--)
        {
            MinHeapify(array, size, i);
        }
        /// 拆除树
        while (size > 0)
        {
            /// 将根与数组最末交换
            swap(array[size-1], array[0]);
            /// 树大小减一
            size--;
            /// 整理树
            MinHeapify(array, size, 0);
        }
        return;
    }
    
    /// --------------       堆排序           ----------------
    
    
    /// --------------       快速排序         ----------------
    /*
        基本思想
        通过第一趟排序，将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分小，然后再对这2部分数据进行排序整个过程可以地柜进行。
        基本介绍
        首先任意选取一个数据，通常选择第一个元素作为关键数据，然后将所有比它小的数据都放到它的前面，所有比它大的数据都放到它后面。
     
        一趟快速排序的算法是：
        1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
        2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
        3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key   的值A[j]，将A[j]和A[i]互换；
        4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
        5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
     
     
     快排的一个循环 
        从最后找比关键值小的。
        从前找比关键之大的。
        合在一起为一个循环。
     */
    template<typename T>
    void Quick_sort(T array[], int low, int high)
    {
        if (low >= high)
        {
            return ;
        }
        int first = low;
        int last = high;
        /// 用第一个元素作为关键值
        int key = array[first];
        
        /// 一个循环= 从后向前 + 从前向后
        while (first < last)
        {
            /// 从最后开始找比关键值大的元素，找到并交换到关键值得位置
            while (first < last && array[last] >= key)
            {
                --last;
            }
            /// 将比第一个小的移动到低端
            array[first] = array[last];
            
            while (first < last && array[first] <= key)
            {
                ++first;
            }
            /// 将比第一个大的移动到高端
            array[last] = array[first];
        }
        
        /// 记录关键值
        array[first] = key;
        /// 递归调用
        Quick_sort(array, low, first - 1);
        Quick_sort(array, first + 1, high);
    }
    /// --------------       快速排序         ----------------
    
    /// --------------       归并排序         ----------------
    
    /*
        算法概述
        该算法是分治法的一个非常典型的应用。
        算法过程：
        比较a[i]与a[j]的大小，若a[i]<= a[j]，则将第一个表中的元素a[i]复制到r[k]中，令i和K分别加上1；
    否则，将第二个有序表中的元素a[j]复制到r[k]中，并令k和j分别+1，如此循环下去。归并算法常采用递归实现。
        
        归并操作示例
     归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
     如　设有数列{6，202，100，301，38，8，1}
     初始状态：6,202,100,301,38,8，1
     第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
     第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
     第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
     总的比较次数为：3+4+4=11,；
     逆序数为14；
     
     */
    template<typename T>
    void Merege(T *sourceArray, T *aimArray, int startIndex, int midIndex, int endIndex)
    {
        int i = startIndex;
        int j = midIndex + 1;
        int k = endIndex;
        
        
        while (i != midIndex && j != midIndex)
        {
            if (sourceArray[i] >= sourceArray[j])
            {
                aimArray[k++] = sourceArray[i++];
            }
            else
            {
                aimArray[k++] = sourceArray[j++];
            }
        }
        
        /// 把剩下的全部合并到新数组中
        while (i != midIndex)
        {
            aimArray[k++] = sourceArray[i++];
        }
        while (j != midIndex)
        {
            aimArray[k++] = sourceArray[j++];
        }
        
        /// 重新归并数组
        for (i = startIndex; i <= endIndex; i++)
        {
            sourceArray[i] = aimArray[i];
        }
    }
    
    template<typename T>
    /// 内部使用递归
    void Merege_sort(T *sourceArr, T *aimArr, int startIndex, int endIndex)
    {
        int midIndex = NULL;
        if(startIndex < endIndex)
        {
            midIndex = (startIndex + endIndex) / 2;
            Merege_sort(sourceArr, aimArr, startIndex, midIndex);
            Merege_sort(sourceArr, aimArr, midIndex+1, endIndex);
            Merege(sourceArr, aimArr, startIndex, midIndex, endIndex);
        }
    }
    
    
    /// --------------       归并排序         ----------------
    
    
    
    
    
    
    
    /*  排序总结 */
    /// 冒泡排序
    void m_Bubble_sort(int *array, int length)
    {
        for (int i = 0; i < length - 1; i++)
        {
            for (int j = 0; j < length - 1 - i; j++)
            {
                if (array[j] > array[j+1])
                {
                    array[j] = array[j] ^ array[j+1];
                    array[j+1] = array[j] ^ array[j+1];
                    array[j] = array[j] ^ array[j+1];
                }
            }
        }
    }
    
    /// 选择排序
    void m_Selectiont_sort(int *array, int length)
    {
        int index = NULL;
        
        for (int i = 0; i < length - 1; i++)
        {
            /// 记录位置
            index = i;
            for (int j = i + 1; j < length; j++)
            {
                /// 判断索引的值是否变化
                if (array[index] > array[j])
                {
                    index = j;
                }
            }
            /// 若不相等，则交换数
            if (index != i)
            {
                array[index] = array[index] ^ array[i];
                array[i] = array[index] ^ array[i];
                array[index] = array[index] ^ array[i];
            }
        }
    }
    
    
    /// 快速排序, 小的数移动到低端，大的数移动到高端
    void m_Quick_sort(int *array, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        /// 定义关键字
        int key = array[first];
        
        while (first < last)
        {
            /// 首先进行的是倒序查找
            while (last > first && array[last] >= key)
            {
                --last;
            }
            array[first] = array[last];
            /// 接着为正序查找
            while (last > first && array[first] <= key)
            {
                ++first;
            }
            ///将第一个大的移动到高端
            array[last] = array[first];
        }
        
        /// 记录枢轴关键字,放到高端
        array[first] = key;
        /// 递归调用
        m_Quick_sort(array, low, first - 1);
        m_Quick_sort(array, first + 1, high);
    }
    
    
    
    
    
    
    /// 快排
    void new_Quick_sort(int *array, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        int key = array[first];
        
        /// first = last ,结束
        while (first < last)
        {
            /// 倒序找，小的， 交换
            while (first < last && array[last] >= key)
            {
                --last;
            }
            array[first] = array[last];
            
            ///  正序找，大的，交换
            while (first < last && array[first] <= key)
            {
                ++first;
            }
            array[last] = array[first];
        }
        array[first] = key;
        new_Quick_sort(array, low, first - 1);
        new_Quick_sort(array, first + 1, high);
    }
    
    /// 快排
    void m_new_Quick_sort(int *array, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        
        int first = low;
        int last = high;
        int key = array[first];
        
        while (first < last)
        {
            while (first < last && array[last] >= key)
            {
                --last;
            }
            array[first] = array[last];
            
            while (first < last && array[first] <= key)
            {
                ++first;
            }
            array[last] = array[first];
        }
        
        ///
        array[first] = key;
        m_new_Quick_sort(array, low, first - 1);
        m_new_Quick_sort(array, first + 1, high);
        
    }
    
    /// 数组输出函数
    void showArray(int *array, int length)
    {
        for (int i = 0; i < length; i++)
        {
            cout << array[i] << " ";
        }
        cout << endl;
    }
    
    
    ///----- 归并排序
    void m_Merege(int *sourceArray, int *aimArray, int startIndex, int midIndex, int endIndex)
    {
        int i = startIndex;
        int j = midIndex + 1;
        int k = startIndex;
        
        
        while (i != midIndex+1 && j != endIndex + 1)
        {
            if (sourceArray[i] >= sourceArray[j])
            {
                aimArray[k++] = sourceArray[j++];
            }
            else
            {
                aimArray[k++] = sourceArray[i++];
            }
        }
        
        /// 把剩下的全部合并到新数组中
        while (i != midIndex+1)
        {
            aimArray[k++] = sourceArray[i++];
        }
        while (j != midIndex+1)
        {
            aimArray[k++] = sourceArray[j++];
        }
        
        /// 重新组合数组
        for (i = startIndex; i <= endIndex; i++)
        {
            sourceArray[i] = aimArray[i];
        }
    }
    
    /// 内部使用递归
    void m_Merege_sort(int *sourceArr, int *aimArr, int startIndex, int endIndex)
    {
        int midIndex = NULL;
        if(startIndex < endIndex)
        {
            midIndex = (startIndex + endIndex) / 2;
            m_Merege_sort(sourceArr, aimArr, startIndex, midIndex);
            m_Merege_sort(sourceArr, aimArr, midIndex+1, endIndex);
            m_Merege(sourceArr, aimArr, startIndex, midIndex, endIndex);
        }
    }
    
    
    
    
    /// 快排_
    void m_Quick_mem_sort(int *arr, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        
        int first = low;
        int last = high;
        int key = arr[first];
        
        
        while (first < last)
        {
            while (first < last && arr[last] >= key){--last;}
            arr[first] = arr[last];
            while (first < last && arr[first] <= key) {++first;}
            arr[last] = arr[first];
        }
        arr[first] = key;
        m_Quick_mem_sort(arr, low, first - 1);
        m_Quick_mem_sort(arr, first+1, high);
    }
    
    
    /// 复习快排
    void quick_sort_review(int *array, int low, int high)
    {
        if (low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        int key = array[first];
        
        while (first < last)
        {
            while (first < last && array[last] >= key)
            {
                --last;
            }
            array[first] = array[last];
            while (first < last && array[first] <= key)
            {
                ++first;
            }
            array[last] = array[first];
        }
        
        array[first] = key;
        
        quick_sort_review(array, low, first - 1);
        quick_sort_review(array, first + 1, high);
    }
    
    
    
    /// 冒泡复习
    void bubble_sort_review(int *arr, int length)
    {
        for (int i = 0; i < length - 1; i++)
        {
            for (int j = 0; j < length - 1 - i; j++)
            {
                if (arr[j] >= arr[j+1])
                {
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
        }
    }
    
    
    /// 选择排序学习
    void select_sort_review(int *arr, int length)
    {
        int index = NULL;
        
        for (int i = 0; i < length - 1; i++)
        {
            index = i;
            for (int j = i; j < length; j++)
            {
                if (arr[j] < arr[index])
                {
                    index = j;
                }
            }
            if (i != index)
            {
                arr[index] = arr[i] ^ arr[index];
                arr[i] = arr[i] ^ arr[index];
                arr[index] = arr[i] ^ arr[index];
            }
        }
    }
    
    
    ///主函数
    int main(int argc, const char * argv[])
    {
        /// 排序测试数组
        int array[8] = {4, 3, 2, 1, 0, -1, -2, -3};
        
        cout << "原数组内容" << endl;
        for (int i = 0; i < 8; i++)
        {
            cout << array[i] << " ";
        }
        
        /// 快排复习
    //    quick_sort_review(array, 0, 7);
    //    showArray(array, 8);
    
    //    ///冒泡复习
    //    bubble_sort_review(array, 8);
    //    cout << endl;
        
        /// 选择复习
        cout << endl;
        select_sort_review(array, 8);
        
        cout << "排序结果" << endl;
        showArray(array, 8);
    
    
        return 0;
    }

[Center]: /images/20220724/18b0ae2aee2745b191326f8a744e113b.png