概述
基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换。直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有。冒泡排序和快速排序。
冒泡排序
算法思想
通过相邻元素之间的比较和交换，使关键字较小的元素逐渐从底部移向顶部，关键字较大的元素逐渐下移(后移)，小的上浮，大的下沉，所以冒泡排序又被称为"起泡"排序。
步骤
第一趟扫描。依次比较(R[n]，R[n-1])，R[n-1]，R[n-2])，...，(R[2]，R[1])，对于每对气泡(R[j+1]，R[j])，若R[j+1]< R[j]，则交换R[j+1]和R[j]的内容。第一趟扫描完毕时，“最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。然后再对R[n]~R[2]的记录进行第二趟排序，使次小关键字的元素被上浮到R[2]中，重复进行，n-1趟后，整个冒泡排序结束。
实例分析
有8个记录的关键字序列为(36，28，45，13，67，36，18，56)，如下图所示为该序列起泡排序的全过程.
注意： 该方法是自后向前扫描的
步骤如下：
该方法是采用自后向前扫描，一般用前向后扫描
第一轮：
① 18和56比较，18比56小，放在56前面，无需变动
② 18和36比较，18比36小，18与36交换位置
③ 18和67比较，18比67小，18与67交换位置
④ 18和13比较，18比13大，无需变动
⑤ 13和45交换，13比45小，交换位置
⑥ 13和28交换，13比28小，交换位置
⑦ 13和36交换，13比36小，交换位置
这样顺序为：13、36、28、45、18、67、36、56
其他几轮也是同样的方法，直到排序完成
算法描述
/*
* 冒泡排序
* 参数说明：
* array -- 待排序的数组
* n -- 数组长度
*/
void BubbleSort(int array[], int n)
{
//采用自底向上扫描数组R[1.. n]做冒泡排序
int i, j, temp;
for (int i = 0; i < n - 1; i++) {
// 每一趟的元素比较，注意 -1, 两个元素的数组推导一下就懂了。
for (int j = 0; j < n - i - 1; j++) {
cout << j << " ，";
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
算法分析
(1)算法的最好时间复杂度
若待排序记录为有序(最好情况)，则一趟扫描完成，关键比较次数为n-1次且没有移动，比较的时间复杂度为O(n)
(2)算法的最坏时间复杂度
若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。总的比较次数为:(n-1)+(n-2)+ ... +1= n(n-1)/2，总的移动次数为3n(n-1)/2。在平均情况下，比较和移动记录的总次数大约为最坏情况下的一半，所以，冒泡排序算法的时间复杂度为O(n^2)。
(3)算法的空间复杂度
冒泡排序的空间复杂度为O(1)，是就地排序
(4)算法稳定性
冒泡排序是稳定的。
快速排序
算法思想
基本思想：首先在当前无序区R[1ow...high]中任取一个记录作为排序比较的基准(不妨设为x)，用此基准将当前无序区划分为两个较小的无序区R[low...i-1]和R[i+1...high]，并使左边的无序区中所有记录的关键字均小于等于基准的关键字，右边的无序区中所有记录的关键字均大于等于基准的关键字，而基准记录x则位于最终排序的位置i上，这个过程称为一趟快速排序(或一次划分)。当R[lowr...i-1]和R[i+1...high]均非空时，分别对它们进行上述划分，直到所有的无序区中的记录均已排好序为止。
一趟快速排序的具体操作是:设两个指针i和j，它们的初值分别为low和high，基准记录x=R[i]，首先从j所指位置起向前搜索找到第一个关键字小于基准x.key的记录存入当前i所指向的位置上，i自增1，然后再从i所指位置起向后搜索，找到第一个关键字大于x .key的记录存入当前;所指向的位置上，j自减1:重复这两步，直至i等于j为止。
简述
- ①选定中心轴数值Pivot(一般选择第一个)
- ②将大于Pivot的数字放在Pivot的右边
- ③将小于Pivot的数字放在Pivot的左边
- ④分别重复上述步骤，直至排序完成
实例分析
排序过程：
详细步骤
选择一个Pivot值45(排序后，左边的值比他小，右边的值比他大)
设置两个指针，分别放置在头部和尾部
比较左边指针是否小于Pivot，是的话放置在左边，否则不动，指针右移
比较右边指针是否大于Pivot，是的话放置在右边，否则不动，指针左移
直到左右指针重合
第一轮：
- ①由于默认45是Pivot，所以45所在的下标，为空，无需比较，比较尾部指针32比45小，放置在45的位置上，左侧指针有数据了，右移(下标为53)，右侧指针由于刚才取走数据为空，保持不变，排序过程第二行
- ②查看左右两指针哪个不为空，进行比较(一般都不为空的话，则从左到右)，左指针当前所在为53，与Pivot进行比较，发现比Pivot大，将53放置到右指针所指向下标上，并将有指针左移一位(移动到36下)，排序过程第三行
- ③查看左右两指针哪个不为空，进行比较，发现左指针为空，右指针指向36，将36与Pivot进行比较，发现比Pivot(45)小，放置到左指针指向的下标(右指针为空)，左指针右移(到18下)，排序过程第四行
- ④查看左右两指针哪个不为空，进行比较，发现右指针为空，左指针指向18，将18与Pivot进行比较，发现比Pivot(45)小，不移动元素，将左指针向右移动一位(指向49)，将其与Pivot进行比较，比Pivot大，将其放置到右指针指向的下标上，右指针左移(指向97)，排序过程第五行、第六行
- ⑤查看左右两指针哪个不为空，进行比较，发现左指针为空，右指针指向97，与Pivot进行比较，比Pivot大，元素不移动，右指针左移(指向13)，排序过程第七行
。。。。
按上面步骤进行比较，直到左右指针重合，该下标即为Pivot放置的位置，即可看到Pivot左边的比他小，右边的比他大，如排序过程最后一行继续重复第一轮操作，直到排序完成
算法描述
/*
* 快速排序
*
* 参数说明：
* a -- 待排序的数组
* l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
* r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
*/
void QuickSort(int a[], int l, int r)
{
if (l < r)
{
int i, j, x;
i = l;
j = r;
x = a[i];
while (i < j)
{
while (i < j && a[j] > x)
j--; // 从右向左找第一个小于x的数
if (i < j)
a[i++] = a[j];
while (i < j && a[i] < x)
i++; // 从左向右找第一个大于x的数
if (i < j)
a[j--] = a[i];
}
a[i] = x;
QuickSort(a, l, i - 1); /* 递归调用 */
QuickSort(a, i + 1, r); /* 递归调用 */
}
}
算法分析
(1)算法时间复杂度
快速排序的时间复杂度为O(nlogn)。快速排序方法被认为是排序时间效率非常高的一种方法，但是，当参加排序的原始序列已经是一个按值有序或基本有序的序列时，快速排序方法的时间效率将降到最低，这种情况下其时间复杂度为o(n^2)
(2)算法空间复杂度
快速排序的空间复杂度为O(log2n)。
(3)算法的稳定性
快速排序方法是一种不稳定的排序方法。