排序的概念
排序:将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序
内部排序:数据全部放在内存中的排序
外部排序:由于数据太多不能全部放在内存中,需要借助外存的排序
常见的排序算法
比较排序
插入排序:直接插入排序,希尔排序
选择排序:直接选择排序,堆排序
交换排序:冒泡排序,快速排序
归并排序:归并排序
非比较排序
计数排序
直接插入排序
思路:
直接插入排序是指在待排序的元素中,假设前面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)
稳定性:稳定