排序算法总结（C++编写的程序）

• 各排序算法的时间复杂度 

• 冒泡排序

　冒泡排序算法的运作如下：

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

对于如下序列{ 6, 5, 3, 1, 8, 7, 2, 4 }实现的过程如下：

 

 

 

 

下面为冒泡排序的具体实现代码：

#include <iostream>
using namespace std;

void BubbleSort(int a[],int len)
{
	int temp = 0;
	for (int i = 0; i < len; ++i)
		for (int j = 0; j < len-1-i; ++j)

		  // if (a[j] < a[j + 1])//从小到大的排列顺序
           if (a[j] < a[j+1])//从大到小的排列顺序
		   {
			 temp = a[j];
			 a[j] = a[j+1];
			 a[j+1] = temp;
		   }
}


int main()
{
	int a[10] = {8,5,2,9,6,3,1,4,7,0};
	int length = sizeof(a) / sizeof(a[0]);

	cout << "冒泡排序的结果为：";
	BubbleSort(a, length);
	for (int i = 0; i < length; i++)
	{
		cout << a[i];
	}
	cout << endl;

	return 0;
}

• 选择排序

它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

上述代码对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如下图：

选择排序的代码实现过程如下：

#include <iostream>
using namespace std;

void SelectSort(int a[], int len)
{
	int temp = 0;
	for (int i = 0; i < len - 1; ++i)
	{
		int min = i;
		for (int j = i + 1; j < len; ++j)
		{
			if (a[j] < a[min])
				min = j;
		}

		if (min != i)
		{
			temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

int main()
{
	int a[10] = {8,5,2,9,6,3,1,4,7,0};
	int length = sizeof(a) / sizeof(a[0]);

	cout << "选择排序的结果为：";
	SelectSort(a, length);
	for (int i = 0; i < length; i++)
	{
		cout << a[i];
	}
	cout << endl;
	return 0;
}