1、排序的分类：

 

1.1内排序：

 

排序的整个过程中，待排序的所有记录全部放在内存中（本文主要介绍内排序的多种方法）

 

1.2外排序：

 

由于排序的记录个数太多，不能同时放在内存，整个排序需要在内外存之间交换数据才能进行

 

2、八大排序：

 

八大排序的时间复杂度，空间复杂度以及稳定性整理如下：

 

冒泡排序：时间复杂度O（n^2），空间复杂度O（1），稳定

 

归并排序，时间复杂度O（nlogn）;空间复杂度O（nlogn），稳定

 

快速排序，时间复杂度O（nlogn），空间复杂度O（logn） 不稳定

 

桶排序 时间复杂度O（n），空间复杂度O（n），稳定

 

简单选择排序 时间复杂度 O（n^2） 空间复杂度O（1）不稳定

 

直接插入排序，时间复杂度O（n^2） 空间复杂度O（1） 稳定的

 

希尔排序 时间复杂度O（n^1.3——1.5） 空间复杂度O（1） 不稳定

 

堆排序 时间复杂度O（nlogn） 空间复杂度O（1） 不稳定

 

2.1冒泡排序

 

2.1.1冒泡排序的规则：

 

两两关键字，如果反序则交换，直到没有反序的记录为止。

 

2.1.2代码：

 

void Bubble_Sort（int arr[], int n）//传入待排序数组，数组元素

 

{

 

bool tag = true;

 

for （int i = 0; i < n-1; i++）//冒泡排序一共进行多少轮（少一轮），

 

{

 

tag = true;

 

for （int j = 0; j <n-1-i; j++）//每一轮交换的次数

 

{

 

if （arr[j] > arr[j+1]）

 

{

 

tag = false;

 

Swap（arr[j], arr[j + 1]）;

 

}

 

}

 

if （tag）

 

{

 

break;

 

}

 

}

 

}

 

2.1.3冒泡排序的优化：

 

void Bubble_Sort（int arr[], int n）

 

{

 

bool flag = true;

 

for （int i = 0; i < n; i++）

 

{

 

flag = true;

 

//从上往下进行

 

for （int j = i; j < n - i - 1; j++）

 

{

 

if （arr[j] < arr[j + 1]）

 

{

 

flag = false;

 

swap（arr[j], arr[j + 1]）;

 

}

 

}

 

if （flag）

 

{

 

break;

 

}

 

flag = false;

 

//从下往上进行

 

for （int k = n - i - 2; k > i; k--）

 

{

 

if （arr[k] < arr[ k - 1]）

 

{

 

flag = false;

 

swap（arr[k], arr[k - 1]）;

 

}

 

}

 

if （flag）

 

{

 

break;

 

}

 

}

 

}