排序算法总结

Share

一些重要的排序算法！

冒泡排序：

冒泡排序算是简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。

步骤：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  • 举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。
    首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。
    同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.
    这样一次冒泡就完了，把最小的数3排到最前面了。
    对剩下的序列依次冒泡就会得到一个有序序列。

冒泡排序的时间复杂度为O(n^2)。

  • 实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/***************************************
* About:    bubble_sort
* Author:   Feng
***************************************/

#include <iostream>
using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len)
{
    int i, j;  T temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
        if (arr[j] > arr[j + 1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
}
//例子
int main()
{
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
 
    cout << endl;
 
    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (int) sizeof(arrf) / sizeof(*arrf);
    bubble_sort(arrf, len);
    for (int i = 0; i < len; i++)
        cout << arrf[i] << ' ';
 
    return 0;
}

插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。
相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？
就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。

  • 举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。

注意在插入一个数的时候要保证这个数前面的数已经有序。

简单插入排序的时间复杂度也是O(n^2)。

步骤：

1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到下一位置中
6、重复步骤2~5

  • 实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/***************************************
* About:    bubble_sort
* Author:   Feng
***************************************/

#include <iostream>
#include <cmath>
using namespace std;

void insert_sort(int *array,int n)
{
	int i,j;
	int temp;
	for(i=1;i<n;i++)////假设第一个数位置时正确的；要往后移，必须要假设第一个。
	{
	   temp=array[i];//待插入的
	   int j=i;
	   //后移 
	   while(j>0 && array[j-1]>temp)
	   {
	   	 array[j]=array[j-1];
	   	 j--;
	   }
	   array[j]=temp;
	  
	} 
}

int main()
{
	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    insert_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
 
    cout << endl; 
    return 0;
}

选择排序

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。
但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

  • 举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。

    其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

    选择排序的时间复杂度为O(n^2)

步骤：

1、在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
2、在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
3、以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕

  • 实现算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 void select_sort(int *array,int n)
{
	for(int i=0;i<n;i++)
	{
		int k=i;
		for(int j=i+1;j<n;j++)
		{
			if(array[j]<array[k])
			{
				k=j;
			}
		}
		if(k!=i)
		{
			int temp=array[i];
			array[i]=array[k];
			array[k]=temp;
		}
	}
}

快速排序

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

  • 值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

  • 举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。

    ** 5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。

    ** 5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描（思考一下为什么？）4比5小停止。然后i扫描，8比5大停止。交换i,j位置。

    ** 5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。

    ** 4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。

步骤

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-完成的时候，此时令循环结束）

  • 实现算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void quick_sort(int *array,int low,int high)
{
	int first=low,last=high;
	if(first >= last)
	{
		return ;
	}
	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);
}

归并排序

归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。

  • 举个例子

步骤

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4、重复步骤3直到某一指针超出序列尾

比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

  • 速度仅次于快速排序，为稳定排序算法

  • 时间复杂度 O(n log n) ，空间复杂度 O(n)

归并排序的算法通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

  • 代码实例
#include <iostream>  
using namespace std;  

//将有二个有序数列a[first...mid]和a[mid...last]合并。  
void __merge(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  

    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  

    while (i <= m)  
        temp[k++] = a[i++];  

    while (j <= n)  
        temp[k++] = a[j++];  

    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  

void __merge_sort(int a[], int first, int last, int temp[])  
{  
    if(first < last)  
    {  
        int mid = (first + last) / 2;  
        __merge_sort(a, first, mid, temp);  
        __merge_sort(a, mid + 1, last, temp);  
        __merge(a, first, mid, last, temp);  
    }  
}  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if(p == NULL)  
    {  
        return false;  
    }  
    else  
    {  
        __merge_sort(a, 0, n - 1, p);  
        delete[] p;  
        return true;  
    }  
}  

int main()  
{  
    const int LEN = 10;  

    int a[LEN] = {23, 40, 45, 19, 12, 16, 90, 39, 87, 71};  

    cout << "Before the merge sort, the Array is:" << endl;  
    for(int i = 0; i < LEN; ++i)  
    {  
        cout << "a[ " << i + 1 << " ] is: "<< a[i] << endl;  
    }  
    cout << endl;  

    MergeSort(a, LEN);  
    cout << "After the merge sort, the Array is:" << endl;  
    for(int i = 0; i < LEN; ++i)  
    {  
        cout << "a[ " << i + 1 << " ] is: "<< a[i] << endl;  
    }  

    return 0;  
}