交换排序算法有哪些具体实现方式？

本文共计1084个文字，预计阅读时间需要5分钟。

冒泡排序 + 描述：冒泡排序是一种简单的排序算法。它通过比较相邻元素的大小，在发现逆序对时进行交换，直到没有逆序对为止。

生活例子：比如水中气泡的排序，体积大的气泡先浮到水面。

基本思想：先无序，后有序，从头开始相邻比较，不断挤压向后排。

排序过程：遍历整个待排序的数组，比较相邻元素的值，如果第一个比第二个大，就交换它们的位置，这样每次遍历都会将一个最大元素冒泡到它应该在的位置。

①冒泡排序

描述：交换排序中最简单的排序方法。

生活例子：水中的气泡，体积大的先浮上来

基本思想：前无序，后有序，从头相邻比较，不断挤压向后冒泡。

排序过程：①整个待排序区分为无序区和有序区，初始有序区为空，无序区包括所有。

②从无序区第一个开始，并与相邻关键码比较，大于则交换，小则继续后移。

③重复②操作。

void BubbleSort(int r[], int n){ int temp, exchange; exchange = n; //先获取整个待排序序列所有记录 while(exchange != 0) { bound = exchange; //获得最后交换位置，因为该位置后的所有都在有序区 exchange = 0; //记录交换位置 for (int i = 1; i < bound; i++) { if (r[i] > r[i+1]){ /***进行交换***/ temp = r[i]; r[i] = r[i+1]; r[i+1] = temp; exchange = i; //记录每一次交换的位置 } } }}

排序过程：①整个待排序区分为无序区和有序区，初始有序区为空，无序区包括所有。

②从无序区第一个开始，并与相邻关键码比较，大于则交换，小则继续后移。

③重复②操作。

复杂度分析：最好的情况下，在一个循环内为正序，只需执行一次，比较了 n-1次，时间复杂度为 O(n)。

O(n2)。

平均的情况下：时间复杂度为： O(n2)。

②快速排序(分区交换排序)

描述：对起泡排序的改进，记录比较和移动向两端进行，关键码较大的移到后面，反之。

过程：①初始化，选第一个作为轴值，并将i，j分别指向最左右侧位置

②右侧扫描，将轴值记录与j 指向的记录进行比较，如果 j 指向的大，则 j--，重复扫描，直到j(右侧)记录小，将轴值记录与 j位置记录交换，i++

③左侧扫面，轴值与i 位置比较，i小则 i++,重复左侧扫描，直到 i大，将轴值与 i 位置记录交换，j--。

④重复②③直到i，j相同。

代码如下：

int Partition(int r[ ], int first, int end) { i=first; j=end; //初始化 while (i<j) { while (i<j && r[i]<= r[j]) j--; //右侧扫描 if (i<j) { r[i]←→r[j]; //将较小记录交换到前面 i++; } while (i<j && r[i]<= r[j]) i++; //左侧扫描 if (i<j) { r[j]←→r[i]; //将较大记录交换到后面 j--; } } retutn i; //i为轴值记录的最终位置 }

然后是对子序列递归

void QuickSort(int r[], int first, int end) { if(first < end) { pivot = Partition(r, first, end); QuickSort(r, first, pivot - 1); QuickSort(r, pivot + 1, end); }}

复杂度分析：最好的情况下，每次划分对一个记录定位后，该记录的左右子侧长度相等，为O(n)

最坏的情况下：待排序记录正序或逆序，O(n2)

平均：O(log2n)