排序的概念
排序：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序
内部排序：数据全部放在内存中的排序
外部排序：由于数据太多不能全部放在内存中，需要借助外存的排序
常见的排序算法
比较排序
插入排序：直接插入排序，希尔排序
选择排序：直接选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序：归并排序
非比较排序
计数排序
直接插入排序
思路：
直接插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的
算法实现
void Insertsort(int* a, int n) { int i = 0; for (i = 0; i < n - 1; i++) { //[0,end],在end+1位置上插入一个数，使[0,end+1]有序 int end = i; int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end + 1] = a[end]; end--; } else { break; } } //跳出循环有两种可能 //1.end已经越界，此时end==-1 //2.找到比tmp小的数据 a[end + 1] = tmp; } }
图形展示
运行结果
直接插入排序的特点
元素集合越接近有序，插入排序的时间效率便越高
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
希尔排序（缩小增量排序）
思路：
先选定一个整数，把待排序的数据按一定距离分成若干小组，对每一组内的数据进行排序；然后逐渐减小距离，重复上面的操作，直到距离为1所有数据被分到一组，结束排序
图形展示
算法实现
void Shellsort(int* a, int n) { int gap = n; while (gap > 0) { gap /= 2; int i = 0; //gap组数据依次多组并排 for (i = 0; i < n - gap; i++) { int end = i; //[0,end],在end+gap位置上插入一个数据使[0,end+gap]有序 int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }
运行结果
希尔排序的特点
希尔排序是对插入排序的优化
当gap>1是称为预排序，目的便是使数组接近有序；gap越大，大的数据可以越快跳到后面，小的数据可以越快跳到前面；gap越小，数据跳的越慢，但也越接近有序；当gap==1时，数组已经接近有序，排序就更加的快
由于gap的取值没有统一的规定，便导致时间复杂度不易计算
稳定性：不稳定
选择排序
思路：
每次从待排序的数据中选出最小的和最大的数据，若这两个数据不是这组数据的第一个，最后一个数据，则将这两个数据与第一个，最后一个数据进行交换；然后再从剩余的数据中重复此操作，直到排完所有数据
算法实现
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void Selectsort(int* a, int n) { int left = 0; int right = n - 1; while (right > left) { int min = left; int max = left; int i = 1; for (i = left+1; i <= right; i++) { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } Swap(&a[left], &a[min]); //如果最大的数据在第一个位置，需要进行调整 if (max == left) { max = min; } Swap(&a[right],&a[max]); left++; right--; } }
选择排序的特点
效率不高
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
堆排序
在上一篇博客中有详细介绍堆排序，这里就不再赘述需要注意的是
升序：建大堆
降序：建小堆
算法实现
void Adjustdown(int* a, int n, int i) { int minchild = 2 * i + 1; while (minchild < n) { if (minchild + 1 < n && a[minchild + 1] > a[minchild]) { minchild++; } if (a[minchild] > a[i]) { Swap(&a[minchild], &a[i]); i = minchild; minchild = 2 * i + 1; } else { break; } } } void Heapsort(int* a, int n) { int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { //向下调整 Adjustdown(a, n, i); } i = 1; while (i < n) { Swap(&a[0], &a[n - i]); Adjustdown(a, n - i, 0); i++; } }
堆排序的特点
效率很高
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
冒泡排序
思路：
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（后一个数大于前一个数）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成
就类似气泡一样，越往后越大
图形展示
算法实现
void Bubblesort(int* a, int n) { int j = 0; for (j = 1; j <= n; j++) { int i = 0; int exchange = 1; for (i = 0; i < n - j; i++) { if (a[i] > a[i+1]) { Swap(&a[i], &a[i + 1]); } else { exchange = 0; } } if (exchange == 1) { break; } } }
冒泡排序的特点
非常容易理解
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
