当前位置:编程学习 > C/C++ >>

从排序开始(一)冒泡排序、插入排序与选择排序

学习算法,怎么可以不懂排序?但很多时候,我们习惯了用 sort 和 qsort,对于具体排序,我们也许真忘光了。我们先从O(n^2)的常用排序开始。
 
冒泡排序(Bubble Sort):
说起排序就不能不说冒泡(Bubble Sort),它非常简单,维基中这样解释“重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端。”
 
复杂度:
最差时间复杂度:O(n^2)
最优时间复杂度:O(n^2)
平均时间复杂度:O(n^2)
 
稳定性:稳定
 
我写冒泡通常这样写:
[cpp] 
void bubbleSort(int arr[],int n)  
{  
    for(int i = 0;i < n;++i)  
    {  
        for(int j = i+1;j < n;++j)  
        {  
            if(arr[i] > arr[j])  
            {  
                int t = arr[j];  
                arr[j] = arr[i];  
                arr[i] = t;  
            }  
        }  
    }  
}  
 
 
 
基本思想是从数组中拿出第一个元素,然后开始和它后面的元素比较,只要发现比它轻,就交换两个元素,这样,一遍过后,最轻(最小)的元素就冒到了数列的顶端。然后第二趟把第二轻的元素冒上来,依此类推,到最后数列就是有序的。一句话说,就是每一次都选出最小的数字,让它冒出来。
冒泡还可以这样写:
[cpp] 
void bubbleSort(int arr[],int n)  
{  
    for(int i = 0;i < n-1;++i)  
    {  
        for(int j = 0;j < n-i-1;++j)  
        {  
            if(arr[j] > arr[j+1])  
            {  
                int t = arr[j+1];  
                arr[j+1] = arr[j];  
                arr[j] = t;  
            }  
        }  
    }  
}    
 
 
 
这是每一次都把最大的元素沉下去。效果是等价的。
冒泡也可以优化,但毕竟是一种效率低下的算法,无法摆平均O(n^2) 的命运。
一种常见的优化就是记录每一次遍历的过程是否有交换值,没有的话说明后面已经是有序的,直接跳出循环
 
[cpp] 
void bubbleSort(int arr[],int n)  
{  
    for(int i = 0;i < n;++i)  
    {  
        bool flag = false;  
        for(int j = i+1;j < n;++j)  
        {  
            if(arr[i] > arr[j])  
            {  
                int t = arr[j];  
                arr[j] = arr[i];  
                arr[i] = t;  
                flag = true;  
            }  
            if(!flag) break;  
        }  
    }  
}  
 
 
 
插入排序(Insertion Sort):
        插入排序(Insertion Sort)也是一种平均O(n^2)的排序算法。“它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。”维基的这幅图很直观的解释了插入排序:
 
算法步骤为:
1、从有序数列 { a[0] } 和无序数列 { a[1],a[2],a[3],…,a[n-1] }开始进行排序;
2、处理第i个元素时(i=1,2,3,…,n-1),数列 { a[0],a[1],a[2],…,a[i-1] }是已有序的,而数列{ a[i],a[i+1],…,a[n-1] }是无序的。用a[i]与a[i-1],a[ i-2],…,a[0]进行比较,找出合适的位置将a[i]插入;
3、重复第二步,共进行n-i次插入处理,数列全部有序。
 
复杂度:
最差时间复杂度:O(n^2)
最优时间复杂度:O(n^2)
平均时间复杂度:O(n^2)
稳定性:稳定
 
实现:
[cpp]  
void insertSort(int arr[], int n)  
{  
    for (int i = 1; i < n; i++)  
        if (arr[i] < arr[i - 1])  
        {  
            int j,t = arr[i];  
            for (j = i - 1; j >= 0 && arr[j] > t; j--)  
                arr[j + 1] = arr[j];  
            arr[j + 1] = t;  
        }  
}  
 
 
选择排序(Selection Sort):
     基本思想为:“首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。”类似于冒泡,也很容易理解,但它的交换次数明显比冒泡少得多,n比较小的时候,选择排序明显比冒泡快。
 
复杂度:
最差时间复杂度:O(n^2)
最优时间复杂度:O(n^2)
平均时间复杂度:O(n^2)
稳定性:不稳定
为什么是不稳定呢?看一个例子:对 4 5 6 4 2 3 进行选择排序。
开始时,我们找到最小元素 2 并把它和第一个元素 4 交换,这时 序列变成 2 5 6 4 4 2 3,好像没有问题是吗?但是,现在,两个 4 的位置和原来的位置相比已经改变了!所以说选择排序时不稳定的。这点要注意,因为也许有时候会在你毫无察觉的情况下导致一些问题。
 
实现:
[cpp] 
void selectionSort(int arr[], int n)  
{  
    for (int i = 0; i < n; i++)  
    {  
        int index = i;  
        //找出最小元素的索引  
        for(int j = i+1;j < n;++j)  
        {  
            if(arr[index] > arr[j])  
                index = j;  
        }  
        //把找到的最小元素和 arr[i] 交换  
        if(index != i)  
        {  
           
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,