C语言--简单排序算法（冒泡、选择、插入）

实现三种简单的排序算法

文章目录 冒泡排序改进改进2 选择排序插入排序执行结果

冒泡排序

每次外层循环，排出一个最大值

void bubbleSort(int arr[], int len) { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 改进 设置排序完成标志，如果排序完成跳出循环通过设置边界，跳过无意义的片段 void bubbleSort2(int arr[], int len) { int border = len - 1; for (int i = 0; i < len; i++) { bool isSorted = true; int lastSwap = 0; for (int j = 0; j < border; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; isSorted = false; lastSwap = j; } } border = lastSwap; if (isSorted) { break; } } } 改进2

双向冒泡排序，又称鸡尾酒排序

void bubbleSort3(int arr[], int len) { for (int i = 0; i < len / 2; i++) { //有序标记，每一轮的初始值都是true bool isSorted = true; //奇数轮，从左向右比较和交换 for (int j = i; j < len - i - 1; j++) { if (arr[j] > arr[j + 1]) { int t1 = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t1; isSorted = false; } } if (isSorted) { break; } //在偶数轮之前，将isSorted重新标记为true isSorted = true; for (int j = len - i - 1; j > i; j--) { if (arr[j] < arr[j - 1]) { int t2 = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = t2; isSorted = false; } } if (isSorted) { break; } } }

动态记录有效边界

void bubbleSort4(int arr[], int len) { int left = 0; int right = len - 1; int lastSwap = 0; while (left < right) { // 奇数轮 lastSwap = left; for (int i = left; i < right; i++) { if (arr[i] > arr[i+1]) { int t1 = arr[i]; arr[i] = arr[i+ 1]; arr[i+ 1] = t1; lastSwap = i; } } // 收缩右边界 right = lastSwap; // 偶数轮 lastSwap = right; for (int i = right; i > left; i--) { if (arr[i] < arr[i - 1]) { int t2 = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = t2; lastSwap = i; } } // 收缩左边界 left = lastSwap; } } 选择排序

每次循环选出一个最小值，放在数组最前面

void selectionSort(int arr[], int len) { for (int i = 0; i < len; i++) { int minIndex = i; for (int j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } 插入排序

每次将一个数加入到已经排好序的数列当中 第一个数是直接排好的

void insertionSort(int arr[], int len) { for (int i = 1; i < len; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } 执行结果 int main() { //定义数组元素 int array[] = {12, 3, 77, 34, 91, 23, 19, 1,45, 37}; int len = sizeof(array) / sizeof(array[0]); insertionSort(array, len); //输出 for (int i = 0; i < len; i++) { printf("%d ", array[i]); } printf("\n"); return 0; }