排序算法总结（不断更新中）

约定不等于承诺〃 2023-03-02 10:11 11阅读 0赞

### 排序算法总结（不断更新中） ###

*  排序算法总结
 *   *  冒泡排序
     *   *  算法描述
         *  代码
     *  选择排序
     *   *  算法描述
         *  代码
     *  插入排序
     *   *  算法描述
         *  代码
     *  快速排序
     *  归并排序

# 排序算法总结 #

**这篇博客我将会总结排序算法，并不断更新，是一个复习排序算法的过程**  
复杂度：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NpbW9uczI0_size_16_color_FFFFFF_t_70]  
相关概念：

*  稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
 *  不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
 *  时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 *  空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

## 冒泡排序 ##

### 算法描述 ###

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *  针对所有的元素重复以上的步骤，除了最后一个；
 *  重复步骤1~3，直到排序完成。

### 代码 ###

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

参考[这篇文章的图][Link 1]  
![aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjMyMzg0NDktMjE0NjE2OTE5Ny5naWY][]

## 选择排序 ##

### 算法描述 ###

经过N轮循环  
每一轮都将剩余没排序的元素中寻找最大或者最小的，然后将最值放入排序完成的元素后面

### 代码 ###

void SelectSort(int *arr, int n)
    {
        
        int i,j;
        for(i=0; i<n; i++)
        {
        
            int min_index = i;
            int min = arr[i];
            for(j=i; j<n; j++)
            {
        
                if(min>arr[j])
                {
        
                    min = arr[j];
                    min_index = j;
                }
            }
            int temp = arr[i];
            arr[i] = min;
            arr[min_index] = temp;
        }
    }

## 插入排序 ##

### 算法描述 ###

遍历一次，每次将后面数字和前面比较，如果比前面小，插入前面的序列中

### 代码 ###

void InsertSort(int* arr, int n){
        
        int temp,p;
        for(int i=1; i < n; i++)
        {
        
            temp=arr[i]; // temp用来记录当前需要插入的元素
            p=i-1;       // p为游标，去往前遍历，寻找比temp小的元素
            while(p>=0 && temp < arr[p]){
        
                arr[p + 1]=arr[p]; // 将比temp大的、排好序的元素往后移
                p--; // 找到退出时，P已经移到比temp第一小的元素下标
            }
            arr[p + 1]=temp; // p+1就是在需要插入的地方，前面的数比temp小，后面的数比temp大
        }
    }

## 快速排序 ##

详见[本博客的快速排序文章][Link 2]

## 归并排序 ##

详见[本博客的归并排序文章][Link 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NpbW9uczI0_size_16_color_FFFFFF_t_70]: /images/20230208/dabfa48497094a6c9c94be3bfd172bd2.png
[Link 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly93d3cuY25ibG9ncy5jb20vb25lcGl4ZWwvYXJ0aWNsZXMvNzY3NDY1OS5odG1s?x-oss-process=image/format,png
[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvODQ5NTg5LzIwMTcxMC84NDk1ODktMjAxNzEwMTUyMjMyMzg0NDktMjE0NjE2OTE5Ny5naWY]: /images/20230208/86e42966bb0e4754a116385ed6defbd5.png
[Link 2]: https://blog.csdn.net/Simons24/article/details/105083263
[Link 3]: https://blog.csdn.net/Simons24/article/details/105206854