冒泡排序

逐个比较相邻元素，如果逆序则交换。每一趟都会让一个元素就位，总共比较 n-1 趟。

n 个元素，需要进行 n - 1 轮冒泡，每次冒泡都会有一个元素就位，所以每轮冒泡的循环次数都会减一。时间复杂度为： 1 + 2 + … + n-1 = n(n-1)/2 = O(n^2)

初始值： 5 4 3 2 1 首轮冒泡： 4 3 2 1 5 最后一个元素就位 第二轮： 3 2 1 4 5 倒数第二个元素就位 ...

基础版冒泡排序

// 冒泡排序，每轮都会排好一个元素 void bubbleSort(int arr[], int count) { int i, j; // n 个元素，需要比较 n-1 轮 for (i = count - 1; i > 0; i--) { // 每轮比较，只需在剩余的 j 个元素中，从头开始比较 j-1 次 for (j = 1; j <= i; j++) { if (arr[j-1] > arr[j]) { swap(arr, j - 1, j); } } } }

提前结束的冒泡排序

上面的冒泡排序，即使剩余元素都已经有序，内层 for 循环中没有发生元素交换，也会继续执行下去。可以设置一个值，在剩余元素都已经就位时提前结束循环：

void bubbleSort(int arr[], int count) { int i, j, sorted; // n 个元素，需要比较 n-1 轮 for (i = count - 1; i > 0; i--) { sorted = 1; // 每轮比较，只需在剩余的 j 个元素中，从头开始比较 j-1 次 for (j = 1; j <= i; j++) { if (arr[j-1] > arr[j]) { swap(arr, j - 1, j); sorted = 0; } } if (sorted == 1) { break; } } }

标记有序区间的冒泡排序

对于 5 4 3 2 1 9 6 7 8 这样的数据，第一轮排序之后，最后的部分元素都会就位，而不是仅仅就位一个元素。如果每次都标记有序的区间，也可以改善冒泡排序的效率：

void bubbleSort(int arr[], int count) { int i, j; int last = count - 1; for (i = count - 1; i > 0; i--) { i = last; for (j = 1; j <= i; j++) { if (arr[j-1] > arr[j]) { swap(arr, j-1, j); last = j; } } } }

选择排序

冒泡排序每次相邻元素的比较，都可能会发生元素的交换。如果在一轮扫描中，只记录最大元素的位置，扫描结束后再判断是否交换，可以略微改善效率。

选择排序，就是冒泡排序的简单改进版，每轮扫描都会选择一个最大元素，如果这个最大元素未就位，则交换。

代码：

// 选择排序，每轮的比较次数跟冒泡一样，但交换次数最多一次 void selectionSort(int arr[], int count) { int i, j, key; for (i = count-1; i > 0; i--) { key = 0; for (j = 1; j <= i; j++) { if (arr[j] > arr[key]) { key = j; } } if (i != key) { swap(arr, i, key); } } }

插入排序

玩扑克牌的时候，我们会把手里的牌排好次序。每次摸一张牌，都会插入到合适的位置。插入排序，就是这个意思。

首先我们把待排序的元素的第一个元素看作有序集合中仅有的元素，然后把第二个元素插入到这个集合的合适位置，然后是第三个，以此类推。

代码执行时，仍然是逐个相邻元素进行比较。每次发现逆序对，就开始执行插入操作，设逆序对前一个元素是 x，后一个元素是 y：

用临时变量 tmp 保存 y 的值。比较 y 和 x，如果逆序，则把 x 的值放入 y 的位置如果 x-1 未越界，则比较 x 和 x-1，如果逆序，则把 x-1 的值放入 x 的位置，然后把 x-1 看做 x重复执行 3，直到越界或非逆序对。把 tmp 的值赋给 x

代码：

// 插入排序，只扫描一轮，只要有逆序对，就将逆序对的后者与之前的元素 // 逐个比较，直到不逆序或越界。将这些元素逐个后移一位，然后插入这个元素 void insertSort(int arr[], int count) { int i, j, tmp; for (i = 1; i < count; i++) { if (arr[i-1] > arr[i]) { tmp = arr[i]; j = i - 1; while(j >= 0 && arr[j] > tmp) { arr[j+1] = arr[j]; j--; } arr[j+1] = tmp; } } }

三种排序的完整代码示例

#include <stdio.h> void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 冒泡排序，每轮都会排好一个元素 void bubbleSort(int arr[], int count) { int i, j; // n 个元素，需要比较 n-1 轮 for (i = count - 1; i > 0; i--) { // 每轮比较，只需在剩余的 j 个元素中，从头开始比较 j-1 次 for (j = 1; j <= i; j++) { if (arr[j-1] > arr[j]) { swap(arr, j - 1, j); } } } } // 选择排序，每轮的比较次数跟冒泡一样，但交换次数最多一次 void selectionSort(int arr[], int count) { int i, j, key; for (i = count-1; i > 0; i--) { key = 0; for (j = 1; j <= i; j++) { if (arr[j] > arr[key]) { key = j; } } if (i != key) { swap(arr, i, key); } } } // 插入排序，只扫描一轮，只要有逆序对，就将逆序对的后者与之前的元素 // 逐个比较，直到不逆序或越界。将这些元素逐个后移一位，然后插入这个元素 void insertSort(int arr[], int count) { int i, j, tmp; for (i = 1; i < count; i++) { if (arr[i-1] > arr[i]) { tmp = arr[i]; j = i - 1; while(j >= 0 && arr[j] > tmp) { arr[j+1] = arr[j]; j--; } arr[j+1] = tmp; } } } int main(void) { int arr[10] = {2, 8, 1, 5, 3, 0, 4, 9, 7, 6}; int count = 10; int i; printf("raw:\t"); for (i = 0; i < 10; i++) { printf("%d ", arr[i]); } // printf("\nbubble:\t"); // bubbleSort(arr, count); // for (i = 0; i < 10; i++) { // printf("%d ", arr[i]); // } // printf("\nselect:\t"); // selectionSort(arr, count); // for (i = 0; i < 10; i++) { // printf("%d ", arr[i]); // } printf("\ninsert:\t"); insertSort(arr, count); for (i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; }

转载于:https://www.cnblogs.com/kika/p/10851496.html