常用排序算法总结

小咪咪 2022-04-01 03:22 281阅读 0赞

## 前言: ##

最近在编程的时候总是遇到关于数组排序的问题,所以就想写一篇博客来总结几种常用的排序方法.我们下面所列举的排序都是升序排序,主要讲述的是算法,降序排序类似.

## 常见的排序方法: ##

(1)冒泡排序

(2)直接插入排序

(3)直接选择排序

## 主要的排序方法(干货来了): ##

### 1.冒泡排序: ###

冒泡排序主要的实现思路是相邻两个数字比较,发生逆序就交换,按照实现的方法不同可以分为先选最大的和先选最小的.下面就是两种方法的实现代码:

**(1)冒泡排序实现代码1:**

for(int i = 0; i < n-1; i++){
        for(int j = 0; j < n-i-1; j++){
            if(n[j] > n[j+1]){
                t = n[j];
                n[j] = n[j+1];
                n[j+1] = t;
            }
         }
    }

从代码来看,最外层循环有n-1次,这是因为只要确定n-1个数后,剩下那一个一定符合排序规律.内层循环只要是指确定一个数的位置所要比较的次数.我们就拿外层第一次循环举例,当i=0时,j=n-i-1=n-1,if语句中,如果当前数组中的这个数比他下一个数大,两个数字就交换位置(因为需要升序排序,前面的数一定比后面的数要小),根据内层循环j的取值,要从n\[0\]比较到n\[n-1\],也就是第一次循环要从所有数中找到最大的一个放到数组最后一个位置,由于这个数字已经确定是最大的,所以下一次内层循环可以减少一次,找到剩下数组中最大的元素放到第n-2个位置.依次类推,冒泡排序就完成了.**(这个冒泡排序可以形象的看作沉底,每次找最大的放在最后)**

**(2)冒泡排序实现代码2:**

for(int i = 0; i < n-1; i++){
        for(int j = n-2; j >= i; j--){
            if(n[j] > n[j+1]){
                t = n[j];
                n[j] = n[j+1];
                n[j+1] = t;
            }
        }
    }

这个冒泡排序的最外层循环也是n-1次,不过他的内层循环是从j=n-2开始的,if判断语句只要n\[j\]大于n\[j+1\]就交换两元素位置,这个相对于上一个来说代码比较清晰,外层每循环一次都会找出该次循环中的最小数方法数组的开头,由于一次循环完后已经知道开头那些元素是最小的了,所以下次循环次数可以减一.**(这个排序方法是真正的冒泡了,每次选最小的放到该次循环的开头)**

### 2.直接插入排序 ###

假设待排序的数据存放在数组n\[0..N-1\]中.排序过程的某一种中间时刻,n被划分成了两个子区间n\[0..i\]和n\[i+1..N-1\].其中:前一个子区间是已经排好序的有序区,后一个子区间则是当前待排序的区域,直接插入排序法的基本操作是将当前无序区中的第一个元素n\[i+1\]插入到有序区n\[0..i\]中的适当位置,使新数组n\[0..i+1\]成为有序数组.

**实现代码如下:**

for(int i = 0; i < n-1; i++){
        if(n[i] > n[i+1]){
            t = n[i+1];
            j = i;
            do{
                n[j+1] = n[j];    //移动已经有序数组部分,只要数比t大就往后移动一个位置
                j--;
            }while(j>=0 && t<n[j])
            n[j+1] = t;
    
         }
    }

最外层循环是n-1次,里面先是一个判断,如果第i个元素比第i+1个元素大,就先记录下i的大小和第n\[j+1\]的值,这是为下面的循环中好将n\[i+1\]插入到数组n的前面有序部分,do..while循环中是将数组中比n\[i+1\]大的元素都向后移动一个位置,这样可以留出位置供n\[i+1\]插入.**(实质:把后面无序的部分的第一个数插入到前面有序数组的合适位置)**

### 3.直接选择排序 ###

假设在第i次排序开始时,数组分为前面的有序区n\[0..i\]和后面的无序区n\[i+1..N-1\],直接排序法的原理是从后无序区中找出最小的一个放在无序区的起始位置n\[i+1\]处,由于无序区的数都大于有序区中的数,所以一次排序后有序区的个数会扩大1,形成新的有序区n\[i+1\].

实现代码如下:

for(int i = 0; i < n-1; i++){
        k = i;                        //利用k来记录无序区最小数组元素的下标
        for(int j = i+1; j < n-1; j++){  //看看i后面的数组元素有没有比i还小的  
            if(n[j] < n[k]){
                k = j;
            }
        }
        if(i != k){  //如果有比i还小的数组元素,则与i进行替换  
            t = n[i];
            n[i] = n[k];
            n[k] = t;
        }
    }

直接选择排序的外层循环一样是n-1次,而他的内层循环是用来找无序区最小数组的下标,if语句的作用是判断无序区的最小数组是不是无序区的第一个数组元素,如果是,就不需要赋值了,这样可以节省运算时间.

今天先更新到这里,以后继续更新~