各种排序算法复杂度比较
冒泡排序
两两比较，从底往上升。
算法原理
由最后一位开始，相邻两数两两比较，小的往上升，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成c++代码实现
void bubble_sort(int arr[], int len)
{
for (int i = 0; i < len - 1; i++)
{
for (int j = len - 1; j > i; j--)
{
if (arr[j] < arr[j - 1])
{
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
选择排序
固定位置，找元素
- 算法原理
- 先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
- c++代码实现
void select_sort(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
int index = i;
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[index])
index = j;
}
if (index != i)
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
插入排序
固定元素找位置
- 算法原理
将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2) - c++代码实现
void insert_sort(int arr[], int len)
{
for (int i = 1; i < len; i ++)
{
int j = i - 1;
int k = arr[i];
while (j > -1 && k < arr[j] )
{
arr[j + 1] = arr[j];
j --;
}
arr[j + 1] = k;
}
}
快速排序
挖坑填数+分治法
- 算法原理
- 选择一个基准元素，第一个或最后一个
- 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分比基准小，另外一部分比基准大
- 此时基准已经在其排好序后的位置
- 然后再分别对这两部分数据用同样的方法进行排序，整个排序过程可以递归进行，直到整个数据变成有序序列。
总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
- c++代码实现
void quick_sort(int arr[], int left, int right)
{
if (left < right)
{
int i = left, j = right, target = arr[left];
while (i < j)
{
while (i < j && arr[j] > target)
j--;
if (i < j)
arr[i++] = arr[j];
while (i < j && arr[i] < target)
i++;
if (i < j)
arr[j] = arr[i];
}
arr[i] = target;
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
}
归并排序
算法原理
假设序列共有n个元素：
将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素
将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
重复步骤2，直到所有元素排序完毕c++代码实现
void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
{
int first = start_index, second = mid_index + 1;
int index = 0;
//比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数,然后再进行比较，直到有数列为空，
while (first < mid_index + 1 && second < end_index + 1)
{
if (arr[first] > arr[second])
temp_arr[index ++] = arr[second ++];
else
temp_arr[index ++] = arr[first ++];
}
//将另一个数列的数据依次取出即可
while (first < mid_index + 1)
{
temp_arr[index ++] = arr[first ++];
}
while (second < end_index + 1)
temp_arr[index ++] = arr[second ++];
for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)
arr[j] = temp_arr[i];
}
void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)
{
if (start_index < end_index)
{
int mid_index = (start_index + end_index) / 2;
merge_sort(arr, temp_arr, start_index, mid_index);
merge_sort(arr, temp_arr, mid_index + 1, end_index);
merge(arr, temp_arr, start_index, mid_index, end_index);
}
}
堆排序
- 算法原理（以最大堆为例）
- 构建大顶堆
- 初始化堆
- 从最后一个非叶节点开始调整
- 每次调节都从父左右节点中选最大的同父节点交换
- 交换之后可能导致被交换的孩子节点不满足堆的性质，需要重新调整
- 将堆顶元素通过最后一个元素 R[n] 交换
- 由于交换后新堆顶可能违反堆的性质，因此需要重新调整为新堆，然后再次将 R[1]与无序区最后一个元素交换
- 构建大顶堆
- 不断重复，直到有序区的个数为n－1
- c++代码实现
/**
* 将数组arr构建大根堆
* @param arr 待调整的数组
* @param i 待调整的数组元素的下标
* @param len 数组的长度
*/
void heap_adjust(int arr[], int i, int len)
{
int child;
int temp;
for (; 2 * i + 1 < len; i = child)
{
child = 2 * i + 1; // 子结点的位置 = 2 * 父结点的位置 + 1
// 得到子结点中键值较大的结点
if (child < len - 1 && arr[child + 1] > arr[child])
child ++;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if (arr[i] < arr[child])
{
temp = arr[i];
arr[i] = arr[child];
arr[child] = temp;
}
else
break;
}
}
/**
* 堆排序算法
*/
void heap_sort(int arr[], int len)
{
int i;
// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
for (int i = len / 2 - 1; i >= 0; i--)
{
heap_adjust(arr, i, len);
}
for (i = len - 1; i > 0; i--)
{
// 将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
heap_adjust(arr, 0, i);
}
}
希尔排序
分组插入排序，又称缩小增量排序
- 算法原理
- 将整个待排元素分割成若干个序列（由相邻某个增量的元素组成）
- 将这些序列分别进行直接插入排序
- 缩减增量，再重复上述步骤
- 待元素基本有序（增量足够小时）在对全体元素进行一次直接插排
- c++代码实现
void shellsort3(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}
基数排序
- 算法原理
- 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中
- 接下来将这些桶子中的数值重新串接起来，成为新的数列
- 根据十位数数值来分配，重复上述步骤
- 续进行以上的动作直至最高位数为止
- c++代码实现
//最大位数
int maxbit(int data[], int n)
{
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
![Uploading 273973-19cf4a1e58b6ebaf_927583.png . . .]
p *= 10;
++d;
}
}
return d;
}
//基数排序
void radixsort(int data[], int n)
{
int d = maxbit(data, n);
int tmp[n];
int count[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
}
计数排序
- 算法原理
- 遍历一遍整个数组，找出数组中最大数和最小数之间的差距 range,然后开辟一个大小为range的数组count并全部初始化为0；
- 再次遍历整个数组，把每个元素的值映射到count的下标index(val –> (val-min))，每映射到一个index，就把count[index]加一；
- 根据统计结果count，把数写会原数组，某个值index要写count[index]遍到原数组，这样，原数组就有序了
- c++代码实现
void CountSort(int *arr, int len)
{
assert(arr);
if(len <= 1)
return ;
int max = arr[0];
int min = arr[0];
//统计数组中的最大值和最小值
for(int i = 0; i < len; ++i)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
int range = max + 1 - min; //得到最大最小值的差距
int *count = new int[range]; //用于记录数组中每个数字出现的次数
for(int i = 0; i < len; ++i) // 初始化
count[i] = 0;
for(int i = 0; i < len; ++i)
count[ arr[i]-min ]++; //arr[i] - min 映射到tmp中的一个下标，该下标下的值是这个数出现的次数
int index = 0;
for(int i = 0; i < range; ++i) //再把临时数组记录的数分别拷贝到原数组中
{
while(count[i]--) //每个下标下拷贝对应的次数
arr[index++] = i + min;
}
}
