交换排序
一. 冒泡排序
现在我们给大家一个无序数组 要求是我们要将最大的数字放到数组最后面去
这个时候大家应该是怎么想的呢？
1.我们可以遍历一遍数组然后找到一个最大的值 放到最后去 （这个我们待会儿讲）
2.我们将这个数字和后面的数字进行比较 如果前面的数字比较大 就交换它们 如果不大于 就比较下面的数字和后面的数字 这样比较一趟 最大的数字就到最后面了
我们首先来谢谢单趟冒泡排序的代码
1. 单趟冒泡排序
也就是将一个数字放到最后的冒泡排序
代码表示如下
void Bubblesort1(int* arr, int size) { // assert assert(arr); // 将最大的数字放到最后面 int i = 0; int tmp = 0; for ( i = 0; i < size - 1; i++) { // 比较大小 if (arr[i]>arr[i+1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; } } }
我们来看看结果
我们发现可以完美运行
2. 多趟排序
我们想想看 既然每次排序能够将最大的数字放到最后去
我们是不是可以在经过（x-1）次排序之后将x个数字排序完成啊
既然如此 我们开始实现完全体的冒泡排序
代码表示如下
void Bubblesort(int* arr, int size) { // assert assert(arr); // i表示躺数 j表示每一趟排序需要做的事情 tmp临时变量 int i = 0; int j = 0; int tmp = 0; for ( i = 0; i < size-1; i++) { for ( j = 0; j < size - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 比较 if (arr[j]>arr[j+1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } }
还是一样我们来看看效果怎么样
可以完美运行
二. 快速排序
这个排序很难 并且会有很多变形
所以我会用单独的一篇博客来介绍
介绍完之后会将连接贴到这篇博客里面
选择排序
一. 选择排序
1. 单趟选择排序
还记不记得我们上面讲的一句话
我们这里设定只要设定一个最大值 依次遍历整个数组 并且在最后将这个最大值放到数字后面就可以
代码表示如下
void selectionsort1(int* arr, int size) { // assert assert(arr); // 设定一个最大值(下标) 遍历整个数组找到最大的 int maxi = 0; int i = 0; for ( i = 0; i < size; i++) { if (arr[i] > arr[maxi]) { maxi = i; } } // 最后交换位置 int tmp = 0; tmp = arr[maxi]; arr[maxi] = arr[size - 1]; arr[size - 1] = tmp; }
2. 完整选择排序
跟冒泡排序的思想及其相似
使用i控制排序的次数
使用j来控制每次排序
整体代码如下
void selectionsort(int* arr, int size) { // assert assert(arr); // 还是一样 i控制多少次 j控制每一次的选择排序 int i = 0; int j = 0; int maxi = 0; int tmp = 0; for ( i = 0; i < size-1; i++) { for (j = 0; j < size - 1 - i; j++) { if (arr[j]>arr[maxi]) { maxi = j; } } tmp = arr[size - 1 - i]; arr[size - 1 - i] = arr[maxi]; arr[maxi] = tmp; } }
二. 堆排序
堆排序已经在前面的博客中介绍了
大家可以参考下我的这篇博客
