C语言——冒泡排序、直接插入排序、直接选择排序、快速排序

大家好，欢迎来到IT知识分享网。

目录

冒泡排序

注释版： 

无注释版

直接插入排序

注释版： 

无注释版：

使用FOR循环实现：

直接选择排序

快速排序

注释版​

无注释版：

冒泡排序

注释版： 

/* 冒泡排序算法 1、每一次循环结束之后，都要找出最大的数据，放到参与比较的这堆数据的最右边。（冒出最大的那个气泡） 2、核心： 拿着左边的数字和右边的数字比对，当 左边 > 右边 的时候，交换位置。 原始数据： 3，2，7，6，8 第一次循环：（最大的跑到最右边） 2，3，7，6，8 3和2比较，2<3,所以2和3交换位置 2，3，7，6，8 虽然不需要交换位置：但是3和7还是需要比较一次 2，3，6，7，8 6<7 6和7交换位置 2，3，6，7，8 虽然不需要交换位置：但是7和8还是需要比较一次 经过第一次循环，此时剩下参与比较的数据：2，3，6，7 第二次循环 2，3，6，7 2和3比较，不需要交换位置 2，3，6，7 3和6比较，不需要交换位置 2，3，6，7 6和7比较，不需要交换位置 经过第二次循环，此时剩下参与比较的数据：2，3，6 第三次循环 2，3，6 2和3比较，不需要交换位置 2，3，6 3和6比较，不需要交换位置 经过第三次循环，此时剩下参与比较的数据：2，3 第四次循环 2，3 2和3比较，不需要交换位置 原始数据:9 8 10 7 6 0 11 第一次循环： 8 9 10 7 6 0 11 第1次比较后：交换 8 9 10 7 6 0 11 第2次比较后：不交换 8 9 7 10 6 0 11 第3次比较后：交换 8 9 7 6 10 0 11 第4次比较后：交换 8 9 7 6 0 10 11 第5次比较后：交换 8 9 7 6 0 10 11 第6次比较后：不交换 最终冒出的最大数据在右边：11 经过第一次循环，此时剩下参与比较的数据： 8 9 7 6 0 10 第二次循环 8 9 7 6 0 10 第1次比较后：不交换 8 7 9 6 0 10 第2次比较后：交换 8 7 6 9 0 10 第3次比较后：交换 8 7 6 0 9 10 第4次比较后：交换 8 7 6 0 9 10 第5次比较后：不交换 最终冒出的最大数据在右边：10 经过第二次循环，此时剩下参与比较的数据： 8 7 6 0 9 第三次循环 7 8 6 0 9 第1次比较后：交换 7 6 8 0 9 第2次比较后：交换 7 6 0 8 9 第3次比较后：交换 7 6 0 8 9 第4次比较后：不交换 最后冒出的最大数据在右边：9 经过第三次循环，此时剩下参与比较的数据：7 6 0 8 第四次循环 6 7 0 8 第1次比较后：交换 6 0 7 8 第2次比较后：交换 6 0 7 8 第3次比较后：不交换 最后冒出的最大数据在右边：8 经过第四次循环，此时剩下参与比较的数据：6 0 7 第五次循环 0 6 7 第1次比较后：交换 0 6 7 第2次比较后：不交换 最后冒出的最大数据在右边：7 经过第五次循环，此时剩下参与比较的数据：0 6 第六次循环 0 6 第1次比较后：不交换 //7条数据比6次 //6条数据比5次 //5条数据比4次 //4条数据比3次 //3条数据比2次 //2条数据比1次 */ #include <stdio.h> void bubble_sort(int arr[],int length) { int i = 0; int j = 0; //10条数据要循环9次，每次经过9次判断。 n条数据，循环n-1次，判断n-1次 //数组长度是：length。要循环n-1次，所以这里是length-1 for(i=length-1 ; i > 0 ; i--) { for(j=0 ; j<i ; j++) { //内层循环里，j < i，就是几条数据循环(数据条数-1)次，如有10条数据，就循环9次 //交换位置 if(arr[j]>arr[j+1]) { int temp; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main() { int arr[] = {9,8,10,6,2,11,23,18,42,16}; int sz = sizeof(arr)/sizeof(arr[0]); //冒泡排序——将较大的数字放到右边 bubble_sort(arr,sz); //数组传参的时候，传递的是首元素的地址。 int i; for (i = 0; i <sz ; ++i) { printf("%d ",arr[i]); //2 6 8 9 10 11 16 18 23 42 } return 0; }

无注释版

#include <stdio.h> void bubble_sort(int arr[],int length) { int i = 0; int j = 0; for(i=length-1 ; i > 0 ; i--) { for(j=0 ; j<i ; j++) { if(arr[j]>arr[j+1]) { int temp; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main() { int arr[] = {9,8,10,6,2,11,23,18,42,16}; int sz = sizeof(arr)/sizeof(arr[0]); bubble_sort(arr,sz); int i; for (i = 0; i <sz ; ++i) { printf("%d ",arr[i]); } return 0; }

直接插入排序

注释版： 

#include <stdio.h> /* * 直接插入排序是插入排序算法中的一种。 * 采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。 * * 例 采用直接插入排序，将无序表3 1 7 5 2 4 9 6进行排序的过程： * - 因为要与上一个元素相比较，所以i初始化为1，这样就可以与下标为0的坐标相比较。 * 也就是将下标为0的元素直接插入有序表中。 * 3 1 7 5 2 4 9 6 有序：3 无序：1 7 5 2 4 9 6 * * - 当i = 1时，a[1] = 1，与a[0]=3进行比较，因为1<3，所以插入到3的左侧。此时： * 1 3 7 5 2 4 9 6 有序：1 3 无序：7 5 2 4 9 6 * * - 当i=2时，a[2] = 7，与有序表中最后一个，也就是3进行比较，7>3，所以插入到3的右侧。 * 1 3 7 5 2 4 9 6 有序：1 3 7 无序：5 2 4 9 6 * * - 当i=3时，a[3] = 5，与有序表中最后一个，也就是7进行比较，7>5，同时5>3，所以插入到5和7的中间 * 1 3 5 7 2 4 9 6 有序：1 3 5 7 无序：2 4 9 6 * * - 当i=4时，a[4] = 2 ，与有序列表中继续进行比较：7>2，且5>2、3>2、2>1 ，所以插入到1和3中间 * 1 2 3 5 7 4 9 6 有序：1 2 3 5 7 无序：4 9 6 * * - 当i=5时，a[5] = 4 ， 比较：7>4，且5>4、4>3 ， 所以插入到3和5的中间。 * 1 2 3 4 5 7 9 6 有序：1 2 3 4 5 7 无序：9 6 * * - 当i=6时，a[6] = 9 ， 比较：9>7，所以插入到7的右侧。 * 1 2 3 4 5 7 9 6 有序：1 2 3 4 5 7 9 无序：6 * * - 当i=7时，a[7] = 6 ， 比较：9>6，且7>6、6>5，所以插入到5和7的中间 * 1 2 3 4 5 6 7 9 有序：1 2 3 4 5 6 7 9 * * 如何进行排序？ * - 排序进行的次数： * 因为要与前一个元素进行比较，所以i从1开始。也就是第一个元素直接放入有序列表。也就是i=1 * 且每两个元素之间进行一次排序。如果有n个元素，就进行n-1次排序。因为是从1开始，所以是i<n。 * 如上例：n=8，i最大=7。也就是i<n时循环，当i>=8时循环停止。更新条件：i++ ，每次加1：每次插入一个元素。 * - 什么时候进行插入？ * 当前元素 < 前一个元素时，才插入元素。 * 如果当前元素 > 有序列表中的最后一元素，则说明当前元素已经有序，不需要做操作。 * - 当前元素 < 前一元素，应如何进行插入？ * 因为是要将当前元素插入，所以将当前元素先保存到中间变量中。 * 插入的位置呢？ * - 与有序列表中最后一个、倒数第二个、倒数第三个...，直到遇到比插入元素小的，插入到这个的后一个位置。 * 实现思路：如果前一个元素比插入元素大，就将其向后移动一个位置。为插入元素腾出位置。 * 直到碰见比插入元素小的元素，就把元素插入到这个元素的后一个位置。而这个位置原本的那个元素，比插入元素要大，已经移动到后一个位置了。 */ void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } void InsertSort(int R[],int n){ //对R数组按递增顺序进行直接插入排序。 int i,j; for(i=1 ; i<n ; i++) { //如果当前元素比前一个元素要小。 if(R[i] < R[i-1]){ //因为要找插入的位置，所以将当前元素存起来。 int tmp = R[i]; //因为要与有序列表中元素进行比较，所以保存有序列表的最后一个元素坐标，也就是：当前元素的前一元素。 //j的坐标：当前元素的前一元素下标。 j = i-1; //不是用下标i的原因：i是要排序的当前元素，其中保存的数要插入到有序列表中使其继续有序，所以不能使用这个坐标。 //在查找位置的同时，将数组中的元素向后移动，为需要插入的元素腾出位置。 do {//因为当前元素比前一元素要小，所以先将前一元素后移到当前位置，腾出前一个位置。 //当前元素位置：存放前一个元素。 R[j+1] = R[j]; j--;//j的坐标前移，与保存好的当前插入元素tmp进行比较。 //判断条件：j的坐标，也就是数组下标最小就是从0开始，不能比0更小。 //并且是：当前元素小于前一元素时才执行元素向后移动，为插入元素腾位置。 }while(j>=0 && tmp<R[j]); //程序执行到这里，说明tmp > R[j] ，也就是j+1的位置就是我们插入元素的位置。 //也就是判断的当前元素，在有序列表中，R[j]是比其小的元素。并且R[j+1]位置的元素，已经移动到了相对于R[j+1]之后的那个位置。 //所以将j+1处存放当前元素。 R[j+1] = tmp; } printf("i= %d @——@ ",i); print(R,n); } } int main() { //int arr[] = {9,8,7,6,5,4,3,2,1,0}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int arr[] = {3,1,7,5,2,4,9,6}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("排序后：\n"); InsertSort(arr,sz); return 0; }

无注释版：

#include <stdio.h> void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } void InsertSort(int R[],int n){ int i,j; for(i=1 ; i<n ; i++) { if(R[i] < R[i-1]){ int tmp = R[i]; j = i-1; do { R[j+1] = R[j]; j--; }while(j>=0 && tmp<R[j]); R[j+1] = tmp; } printf("i= %d @——@ ",i); print(R,n); } } int main() { //int arr[] = {9,8,7,6,5,4,3,2,1,0}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int arr[] = {3,1,7,5,2,4,9,6}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("排序后：\n"); InsertSort(arr,sz); return 0; }

使用FOR循环实现：

#include <stdio.h> void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } void InsertSort(int arr[],int n){ int i,j; //首元素不用判断，从第二个元素（下标为1的元素）开始判断 for(i=1 ; i<n ; i++) { //i表示当前插入元素，所以不能直接修改。 //创建j，存放i。通过改变j，来与当前元素前面的所有元素进行比较，直到前一个元素不再比当前元素要大时，就跳出循环。 for(j=i ; j>0 ; j--) { //如果当前元素比前一个元素要小，就交换这两个元素。 if(arr[j] <arr[j-1]) { int tmp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = tmp; } else { //执行到这里说明当前元素比前一个元素大。就结束当前循环。 break; } } printf("i= %d @——@ ",i); print(arr,n); } } int main() { //int arr[] = {9,8,7,6,5,4,3,2,1,0}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int arr[] = {3,1,7,5,2,4,9,6}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("排序后：\n"); InsertSort(arr,sz); return 0; }

直接选择排序

#include <stdio.h> /* * 直接选择排序 * 实现思想： * - 对于具有n个数的无序表，遍历 n-1 次。 * 如果执行到最后一个元素，则其后面没有数字，所以最后一个元素的位置本身就是确定的。从0开始，到<n-1 * - 第i次，从无序表中第 i 个数开始，找出后序关键字中最小的记录，然后放置在第 i 的位置上。 */ void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } void SelectSort(int R[], int n) { int i, j, k; for (i=0 ; i<n-1 ; i++) { //将当前坐标保存起来。 k = i; //从当前坐标向后开始寻找最小的数 for (j=i+1 ; j<n ; j++) { //如果后续列表中有比当前元素小的。 if (R[j] < R[k]) { //就把这个最下元素的下标，保存到k中。 k = j; } } //循环结束后，k中保存的就是最小元素的下标。 //如果当前元素不是最小的，也就是说k!=i时，就交换这两个元素。 if(k!=i) { //使用中间变量保存k元素。 int tmp = R[k]; //k中放i元素 R[k] = R[i]; //i中放：存起来的k元素 R[i] = tmp; //就完成了交换 } printf("i= %d @——@ ",i); print(R,n); } } int main() { int arr[] = {6,8,7,9,0,1,3,2,4,5}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("排序后：\n"); SelectSort(arr,sz); /* 排序前： 6 8 7 9 0 1 3 2 4 5 排序后： i= 0 @——@ 0 8 7 9 6 1 3 2 4 5 i= 1 @——@ 0 1 7 9 6 8 3 2 4 5 i= 2 @——@ 0 1 2 9 6 8 3 7 4 5 i= 3 @——@ 0 1 2 3 6 8 9 7 4 5 i= 4 @——@ 0 1 2 3 4 8 9 7 6 5 i= 5 @——@ 0 1 2 3 4 5 9 7 6 8 i= 6 @——@ 0 1 2 3 4 5 6 7 9 8 i= 7 @——@ 0 1 2 3 4 5 6 7 9 8 i= 8 @——@ 0 1 2 3 4 5 6 7 8 9 */ return 0; }

快速排序

注释版​

 /* * 快速排序。 * 假设对： 6 8 7 9 0 1 3 2 4 5进行排序。 * - 第一个数6作为基准数。将这个序列中，所有比基准数大的，放到6的右边。小的放到左边。 * * 实现思路：分别从”6 8 7 9 0 1 3 2 4 5“两端开始探测。 * - 将最左边的数6作为基准数，保存起来。left指向数组开头，right指向数组结尾。 * - 先从右往左找一个小于6的数，再从左往右找一个大于6的数。 * 右往左比6小的：5 ，放到原来6所在的位置上。left++，此时left指向第二个数，第二个数比6大，所以放到原来数字5的位置。 * - 继续从右往左找比6小的：4，放到原来数字8所在的位置。left++，指向第三个数，第三个数比6大， 放到原来4的位置。 * - 继续从右往左找比6小的：2，放到原来7的位置。left++，指向第四个数，第四个数比6大，放到原来2的位置。 * - 继续从右往左找比6小的：3，放到原来9的位置，left++，指向第五个数，第五个数0比6要小，继续++ * - 此时从左往右继续：第6个数1比6小，继续++，此时left指向了第七个数，而right也指向第7个数，也就是数字3的位置。 * 将保存的6放到3的位置上，就完成了第一轮交换。此时6的左边，都是比6小的，6的右边，都是比6大的。 * ...... * - 然后递归调用，先为左边区域排序，再为右边区域排序。 */ #include <stdio.h> void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } int Partition(int array[],int left,int right) { if(left>right) return 0; //temp为基准数。 //因为设置的基准数是最左边的数字，所以从最右边开始 int temp = array[left]; //当i在j的左边的时候执行循环。 当left=right的时候循环就停止。 while(left < right) { //如果left<right，并且right下标元素大于基准数时，从右往左，找小于基准数的数。 while(left<right && array[right]>=temp) right--; //如果找到的比基准数大，就right--。直到找到比基准数小的元素。 //将比基准数小的数放到left的位置上。 array[left] = array[right]; //从左往右，找大于基准数的数。 while(left<right && array[left]<=temp) left++;//如果找到的比基准数小，就left++。直到找到比基准数大的元素。 //将找到的这个数（比基准数大）放到刚刚的right（右边的比基准数小的数的）位置上 array[right] = array[left]; } array[left] = temp; printf("left:%d， right:%d —— ",left,right); print(array,10); return left; } void QuickSort(int array[],int left,int right) { if (left < right) { //划分左右区间 int mid = Partition(array, left, right); //对左区间递归排序 QuickSort(array, left, mid - 1); //对右区间递归排序 QuickSort(array, mid + 1, right); } } int main() { int arr[] = {6,8,7,9,0,1,3,2,4,5}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("——————————————————————————————\n"); QuickSort(arr,0,sz-1); printf("排序后：\n"); print(arr,sz); /* 排序前： 6 8 7 9 0 1 3 2 4 5 —————————————————————————————— left:6， right:6 —— 5 4 2 3 0 1 6 9 7 8 left:5， right:5 —— 1 4 2 3 0 5 6 9 7 8 left:1， right:1 —— 0 1 2 3 4 5 6 9 7 8 left:2， right:2 —— 0 1 2 3 4 5 6 9 7 8 left:3， right:3 —— 0 1 2 3 4 5 6 9 7 8 left:9， right:9 —— 0 1 2 3 4 5 6 8 7 9 left:8， right:8 —— 0 1 2 3 4 5 6 7 8 9 排序后： 0 1 2 3 4 5 6 7 8 9 */ return 0; }

无注释版：

#include <stdio.h> void print(int arr[],int n){ int i; for(i=0 ; i<n ; i++) { printf("%d ",arr[i]); } printf("\n"); } int Partition(int array[],int left,int right) { if(left>right) return 0; int temp = array[left]; while(left < right) { while(left<right && array[right]>=temp) right--; array[left] = array[right]; while(left<right && array[left]<=temp) array[right] = array[left]; } array[left] = temp; printf("left:%d， right:%d —— ",left,right); print(array,10); return left; } void QuickSort(int array[],int left,int right) { if (left < right) { int mid = Partition(array, left, right); QuickSort(array, left, mid - 1); QuickSort(array, mid + 1, right); } } int main() { int arr[] = {6,8,7,9,0,1,3,2,4,5}; //int arr[] = {15,220,35,20,36,88,153,22,182,143}; int sz = sizeof(arr) / sizeof(int); printf("排序前：\n"); print(arr,sz); printf("——————————————————————————————\n"); QuickSort(arr,0,sz-1); printf("排序后：\n"); print(arr,sz); return 0; }