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

实现三种简单的排序算法

冒泡排序

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

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;}}}
}

改进

1. 设置排序完成标志，如果排序完成跳出循环
2. 通过设置边界，跳过无意义的片段

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++) {//有序标记，每一轮的初始值都是truebool 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重新标记为trueisSorted = 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;
}