前言
原来在前面数据结构与算法那里整理了七大常见算法,现在打算在其基础上再增加三个算法供大家伙参考。
推荐个网站可以看动态排序算法，更好地帮助你理解
冒泡排序
* 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
* 针对所有的元素重复以上的步骤，除了最后一个；
* 重复步骤1~3，直到排序完成。
图解冒泡
代码实现
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubblesort(int* a, int n) { //10,6,7,1,3,9,4,2 for (int i = 0; i < n - 1; i++)//趟数 { for (int j = 0; j < n - 1 - i; j++)//比较次数 { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); } } } }
冒泡优化
冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，都先循环比较。 比如我举个数组例子：[1,2,3,4,5]，一个有序的数组，根本不需要排序，它仍然是双层循环一个不少的把数据遍历干净，这其实就是做了没必要做的事情，属于浪费资源。针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了.
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubblesort(int* a, int n) { //10,6,7,1,3,9,4,2 for (int i = 0; i < n - 1; i++)//趟数 { int flag=0; for (int j = 0; j < n - 1 - i; j++)//比较次数 { if (a[j] > a[j + 1]) { swap(&a[j], &a[j + 1]); flag=1; } } if(flag==0) break; } }
冒泡排序的特征总结:
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
图解选排
代码实现
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void selectsort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++)//走访未排列的元素 { if (a[j] < a[min])//找到目前最小值 min = j;//记录最小值 } swap(&a[min], &a[i]); } }
直接选择排序的特征总结:
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
插入排序
* 从第一个元素开始,该元素可以认为已经被排序;
* 取出下一个元素，在已经排序的元素序列中从后向前扫描；
* 如果该元素（已排序）大于新元素，将该元素移到下一位置；
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
* 将新元素插入到该位置后；
* 重复步骤2~5。
图解插入
代码实现
void InsertSort(int* a, int n) { //n:待排序数字的个数;n=sizeof(a)/sizeof(int); assert(a);//函数断言 for (int i = 0; i < n - 1; ++i) { // 将x插入[0, end]有序区间 int end = i; int x = a[end+1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; --end; } else { break; } } a[end + 1] = x; } }
直接插入排序特性总结:
1.元素集合越接近有序，直接插入排序算法的时间效率越高;
2. 时间复杂度：O(N^2) ;
3. 空间复杂度：O(1)，它是一种稳定的排序算法 ;
4. 稳定性：稳定;
希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所 有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后 取, 重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。
图解希尔
代码实现:
void ShellSort(int* a, int n) { //n:待排序数字的个数;n=sizeof(a)/sizeof(int); // 多次预排序(gap > 1) +直接插入 (gap == 1) int gap = n; while (gap > 1) { //gap = gap / 2; gap = gap / 3 + 1; // 多组并排 for (int i = 0; i < n - gap; ++i) { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } } }
希尔排序的特性总结:
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的 了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对 比。
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3 — N^2）
4. 稳定性：不稳定
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
* 把长度为n的输入序列分成两个长度为n/2的子序列；
* 对这两个子序列分别采用归并排序；
* 将两个排序好的子序列合并成一个最终的排序序列。
图解归并
代码实现
递归
void _MergeSort(int* a, int left, int right, int* tmp) { if (left >= right) { return; } int mid = (left + right) / 2; // [left, mid] [mid+1, right] 有序 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); int begin1 = left, end1 = mid; int begin2 = mid+1, end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } // tmp 数组拷贝回a for (int j = left; j <= right; ++j) { a[j] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
非递归
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { // [i,i+gap-1] [i+gap,i+2*gap-1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // 核心思想：end1、begin2、end2都有可能越界 // end1越界 或者 begin2 越界都不需要归并 if (end1 >= n || begin2 >= n) { break; } // end2 越界，需要归并，修正end2 if (end2 >= n) { end2 = n- 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 把归并小区间拷贝回原数组 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = NULL; }
归并排序的特征总结:
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外 排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
