几个基础概念:
稳定:如果原数组中a在b的前面a与b相等,且排序之后a仍然在b的前面,称为该算法稳定。否则为不稳定。
排序算法中经常用到排序的起始位置和数组长度以及交换操作。
注意:有些传入函数的参数是数组和数组长度,而有一些是数组和左下标及右下标。
//起始位置
int start = 0;
//数组长度
int length = sizeof(arr)/sizeof(int);
//交换两个数值的函数
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
1.冒泡排序bubble sort
通过对待排序序列从前到后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素之间从前部移到后部。前后两个指针,每一轮确定当前的最大值位置。
逆序交换
时间复杂度:O(n^2)。
空间复杂度:O(1)。
是否稳定:稳定。
void bubble_sort(int arr[],int length){
for(int i = 0;i<length;i++){
for(int j = 0;j < length;j++){
if(q[i] > q[j]) swap(q[i],q[j]);
}
}
}
调用方法:
bubble_sort(arr, length);
2.选择排序selection sort
第一次找出arr[0,n-1]中确定最小值和arr[0]交换,第二次找出arr[1,n-1]中确定最小值和arr[1]交换......
最小值交换
时间复杂度:O(n^2)
空间复杂度:O(1)
是否稳定:不稳定
void selection_sort(int arr[],int length) {
int min ;
//事实上遍历length-1次也是可以的
for (int i = 0; i < length ; i++) {
//每次找到从i+1到length的最小值
min = i;
for (int j = i + 1; j < length; j++) {
if (arr[min] > arr[j]) min = j;
}
swap(arr[min], arr[i]);
}
}
3.快速排序
快速排序先找到一个基准值,使得数组分为两部分:左边都是小于该基准值的数,右边都是大于该基准值的数。然后对左右两部分再以同样的方法排序。
时间复杂度:O(nlogn)
空间复杂度:O(1)
是否稳定:不稳定
void quick_sort(int arr[], int left, int right) {
if (left >= right)return;
int i = left - 1, j = right + 1;
//以中间点作为基准值
int x = arr[(left + right) / 2];
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
//左边大于x的数和右边小于x的数交换
if (i < j)swap(arr[i], arr[j]);
}
//分别对左右两边以同样的方法排序,注意边界
quick_sort(arr, left, j);
quick_sort(arr, j + 1, right);
}
调用方法:注意这里的 left 和 right 是下标,尤其是 right 需要 length-1.
quick_sort(arr,start,length-1)
4.归并排序merge sort
归并排序基于分治思想,首先确定分界点,然后递归排序左边和右边,最后再把两个部分合并起来。归并排序需要一个中间数组。
时间复杂度:O(nlogn)
空间复杂度:O(n)
是否稳定:稳定
//额外数组
int temp[N];
void merge_sort(int arr[], int left, int right) {
if (left >= right)return;
//确定分界点
int mid = (left + right) / 2;
//递归排序left right
merge_sort(arr, left, mid), merge_sort(arr, mid + 1, right);
//归并合二为一
int k = 0, i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] < arr[j])temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid)temp[k++] = arr[i++];
while (j <= right)temp[k++] = arr[j++];
//复制回去
for (i = left, j = 0; i <= right; i++, j++) {
arr[i] = temp[j];
}
}
调用方法:
merge_sort(arr,start,length-1);
5.插入排序insertion sort
插入排序类似于扑克牌的整理,先把下标为0的数看成是有序的,从下标为1的数开始与前一个数相比较。只要比前面的数值小就要往前排。
时间复杂度:O(n^2)
空间复杂度:O(1)
是否稳定:稳定
void insertion_sort(int arr[], int length) {
for (int i = 0; i < length ; i++) {
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr[j], arr[j - 1]);
}
}
}
void insertion_sort2(int arr[], int length) {
for (int i = 1; i < length; i++) {
//先保存要插入的数
int insertVal = arr[i];
int insertIdx = i-1;
//只要不越界并且满足要插入的数小于前面的数
while (insertIdx>=0&&insertVal<arr[insertIdx]) {
arr[insertIdx++] = insertVal;
insertIdx--;
}
//当退出循环时说明插入的位置是insertIdx+1
arr[insertIdx + 1] = insertVal;
}
}
6.堆排序heap sort
先把数组构造成一个大顶堆(父节点大于子节点),然后把堆顶(数组最大值,数组第一个元素)和数组最后一个元素交换,这样就把最大值放到了数组最后边。把数组长度减一,在进行构造堆。
时间复杂度:O(nlogn)
空间复杂度:O(1)
是否稳定:不稳定
void adjust_heap(int a[], int x, int n)
{
//x是待调整结点的下标,n是待调整的最后一个元素的下标
int l = x * 2 + 1;//左子结点的下标
int r = x * 2 + 2;//右子结点的下标
int max = x;
if (l < n && a[l] > a[max]) max = l;
if (r < n && a[r] > a[max]) max = r;
if (max != x)
{
swap(a[x], a[max]);
adjust_heap(a, max, n);
}
}
void heap_sort(int arr[], int length)
{
for (int i = length / 2 - 1; i >= 0; i--)
adjust_heap(arr, i, length); //建初始堆
//进行n-1次排序
for (int i = length - 1; i > 0; i--)
{
swap(arr[0], arr[i]); //根结点与最后一个元素交换
adjust_heap(arr, 0, i); //对数组重新建堆
}
}
7.计数排序
桶思想的一种,是一种非比较排序,将整数按位数切割成不同的数字,然后按每个位数分别比较。适用于整数数字量很大但是数值的范围小且已知的情况下。开辟一个数组,数组的下标作为代表的值,array[ i ]表示在数值 i 有array[ i ]个。
例:某大型企业员工的年龄排序,快速得知高考名次。
时间复杂度:O(n)
void bucket_sort(int arr[], int length) {
//这里设arr数组的数值范围在[0,100]则需要开辟一个101个值的数组
//并且初始化为不在数值范围的数
int count[103] = {0};
//计数
for (int i = 0; i < length; i++) count[arr[i]]++;
//再把临时数组的值赋给原数组
int count_size = sizeof(count) / sizeof(int);
for (int i = 0, j = 0; i < count_size; i++) {
while (count[i]-- > 0)arr[j++] = i;
}
}
8.希尔排序shell sort
是基于插入排序的一种更高效的排序方法,也称为缩小增量排序。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减到1整个数组正好分成一组,算法终止。
时间复杂度:
空间复杂度:
是否稳定:
①基于交换的希尔排序:找到一个就交换一个。
void shell_sort1(int arr[], int length) {
int temp = 0;
//每次一组的大小为一半
for (int gap = length / 2; gap > 0; gap /= 2) {
//下标i和下标j的数分别表示对比的两组
//遍历各组中所有元素(共gap组,每组为length/gap个数据)步长gap
for (int i = gap; i < length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长后的那个元素,交换
if (arr[j] > arr[j + gap])swap(arr[j], arr[j + gap]);
}
}
}
}
②基于移位的希尔排序(更快)
void shell_sort2(int arr[],int length) {
//增量每次都/2
for (int step = length / 2; step > 0; step /= 2) {
//从增量那组开始进行插入排序,直至完毕
for (int i = step; i < length; i++) {
int j = i;
int temp = arr[j];
//arr[j]和arr[j-step]是要移动的一组数
while (j - step >= 0 && arr[j - step] > temp) {
arr[j] = arr[j - step];
j = j - step;
}
//循环结束则找到那个temp的位置。
arr[j] = temp;
}
}
}
|