c++十大排序——冒泡排序_c++冒泡排序

算法基本知识铺垫

有些人可能不知道什么是稳定排序、原地排序、时间复杂度、空间复杂度，我这里先简单解释一下：

1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序

2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储 空间进行比较和交换的数据排序。

4、非原地排序：需要利用额外的数组来辅助排序。

5、时间复杂度：一个算法执行所消耗的时间。

6、空间复杂度：运行完一个算法所需的内存大小

十大排序一览图

十大排序中的稳定排序

冒泡排序（bubble sort） — O(n2)

插入排序 （insertion sort）— O(n2)

归并排序 （merge sort）— O(n log n)

十大排序中的非稳定排序

     面试考察中一般问快排，选择，希尔，堆这几种非稳定排序

选择排序 selection sort）— O(n2)

希尔排序 （shell sort）— O(n log n)

堆排序 （heapsort）— O(n log n)

快速排序 （quicksort）— O(n log n)

冒泡排序思想

将第一个元素和第二个元素进行比较，若为逆序则将两个元素交换，然后比较第二个元素和第三个元素。依次类推，直至第 n-1个元素和第 n个元素进行比较为止。上述过程称为第一趟冒泡排序，其结果使最大值元素被放置在最后一个位置（第 n个位置）。然后进行第二趟冒泡排序，对前 n-1个元素进行同样操作，其结果是使第二大元素被放置在倒数第二个位置上（第 n-1个位置）。

冒泡排序图解

黄色表示已排序部分，蓝色表示未排序部分。

代码实现 

#include<iostream>
using namespace std;
//-------------------普通冒泡排序算法--------------
void mySwap(int &a, int &b) {
  int temp = a;
	a = b;
	b = temp;
}
 
 
void bubbleSort(int arr[],int length)
{
	for (int i = 0; i < length-1 ; i++){
		for (int j = 0; j < length-1  - i; j++){
			if(arr[j]>arr[j+1]){
				int temp;
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;   
				//mySwap(arr[j], arr[j + 1]);
				//直接自己写的mySwap交换函数也可以，就当自己练习引用传递了
			}
		}
	}
}
//-----------------优化冒泡排序------------记录每轮是否进行过交换
void bubbleSort_better(int arr[], int length)
{
	bool isSorted = false;
	for (int i = 0; i < length - 1; i++){
		isSorted = false;
		for (int j = 0; j < length - 1 - i; j++){
			if (arr[j] > arr[j + 1]){
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				//mySwap(arr[j], arr[j + 1]);
				//直接自己写的mySwap交换函数也可以，就当自己练习引用传递了
				isSorted = true;
			}
		}
		if (isSorted) break;
	}
 
}
 
int main()
{
	int arr[] = { 9,1,2,3,4,5,6,7,8 };
	int length = sizeof(arr) / sizeof(arr[0]);
	//bubbleSort(arr,length);;
	bubbleSort_better(arr, length);
	for (int i=0;i<9;i++)
	{
		cout << arr[i] << ' ';
	}
	
	return 0;
}