学习了十种常见的排序方法,此文章针对所学的排序方法进行整理(通过C语言完成排序)。
参考内容:
https://blog.csdn.net/mwj327720862/article/details/80498455
https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
1. 冒泡排序(Bubble Sort)
冒泡排序是一种简单的排序算法,属于交换排序的一种。通过重复遍历待排序的列表,依次比较相邻的两个元素并根据大小进行交换。
- 从左到右依次比较相邻的两个元素,如果前面的元素大于后面的元素,就交换它们的位置。
- 重复此过程,将最大(或最小)的元素移动到当前未排序部分的末尾。
- 对未排序部分重复上述步骤,直到所有元素都排好序。
时间复杂度(平均): O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( 1 ) O(1) O(1)
如图中数组排序,用了5轮成功排好序,但实际运行了8轮(不判断数组已经有序的情况下),以下是排序实现代码。
#include <stdio.h>
int bubbleSort(int arr[],int size)
{
for(int i = 0; i < size - 1; i++)
{
for(int j = 0; j <size - i - 1;j++)
{
if(arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void printArr(int arr[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%-5d",arr[i]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
bubbleSort(arr,size);
printArr(arr,size);
return 0;
}
2. 选择排序(Selection Sort)
选择排序是一种简单排序算法,它的基本思想是通过多次选择,将没排序部分中的最小(或最大)元素找到,将其放在已排序部分的末尾(或开头)。
- 从未排序部分中找到最小(或最大)的元素。
- 将该元素与未排序部分的第一个元素交换,完成一轮排序。
- 将剩余未排序部分重复上述步骤,直到所有元素都排序完成。
时间复杂度(平均): O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( 1 ) O(1) O(1)
#include <stdio.h>
int selectSort(int arr[],int size)
{
int i,j,k;
for(i = 0; i < size - 1; i++)
{
k = i;
for(j = i + 1; j < size; j++)
{
if(arr[k] > arr[j])
k = j;
}
int temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
int printArr(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%-5d",arr[i]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
selectSort(arr,size);
printArr(arr,size);
return 0;
}
3. 插入排序(Insert Sort)
插入排序是一种简单的排序算法,它的基本思想是:将待排序的数组划分为已排序部分和未排序部分,每次从未排序部分取出一个元素,插入到已排序部分的合适位置,直到整个数组变得有序。
- 从第二个元素开始,依次将未排序部分的元素插入到已排序部分的合适位置,使已排序部分始终有序。
- 重复上述步骤,直到所有元素都排好序。
时间复杂度(平均): O ( n 2 ) O(n^2) O(n2)
空间复杂度:
O
(
1
)
O(1)
O(1)
#include <stdio.h>
int insertSort(int arr[],int size)
{
int i,j;
for( i = 1; i < size; i++)
{
int temp = arr[i];
for(j = i; j > 0 && arr[j - 1] > temp; j--)
{
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
void printArr(int arr[], int size)
{
for(int i = 0; i < size; i++)
printf("%-5d",arr[i]);
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
insertSort(arr,size);
printArr(arr,size);
return 0;
}
4. 希尔排序(Shell Sort)
希尔排序是一种基于插入排序的高级排序算法,它的基本思想是通过逐步减少数据的间隔(gap),将数据分组并排序,从而逐步逼近整体有序;它的核心思想是分组插入排序,通过对数据进行预排序以减少逆序对,从而优化了插入排序的效率。
- 将数组分成多个间隔为gap的子序列(每隔gap个元素视为一个分组)。
- 对每个子序列进行插入排序,使子序列内局部有序。
- 减小gap值,重复步骤 1 和 2,直到gap=1,此时对整个数组进行最后一次插入排序。
- 最终数组完全有序
时间复杂度(平均):介于 O ( n l o g n ) O(nlog n) O(nlogn)和 O ( n 2 ) O(n^2) O(n2)之间
空间复杂度: O ( 1 ) O(1) O(1)
#include <stdio.h>
int shellSort(int arr[],int size)
{
int i,j,temp,increment;
for(increment = size / 2; increment > 0; increment /= 2)
{
for(i = increment; i < size; i++)
{
temp = arr[i];
for(j = i - increment; j >= 0 && arr[j] > temp; j -= increment)
{
arr[j + increment] = arr[j];
}
arr[j + increment] = temp;
}
}
}
void printArr(int arr[],int size)
{
for(int i = 0; i < size; i++)
printf("%-5d",arr[i]);
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
shellSort(arr,size);
printArr(arr,size);
return 0;
}
5. 归并排序(Merge Sort)
归并排序是一种分治算法,它通过将数组不断拆分成更小的子数组进行排序,并将排序后的子数组合并成一个有序的数组。它的主要思想是分而治之:
- 分解:将数组递归地分成两半,直到每个子数组只有一个元素或为空。
- 合并:将两个有序的子数组合并成一个更大的有序数组。
- 将数组从中间拆分成两个子数组。
- 递归地对左右两个子数组进行归并排序。
- 合并两个有序子数组,使整个数组有序。
时间复杂度(平均): O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( n ) O(n) O(n)(需要额外数组存储合并结果)
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for(int i = 0; i < n1; i++)
L[i] = arr[left + i];
for(int i = 0; i < n2; i++)
R[i] = arr[mid +i + 1];
int i = 0, j = 0, k = left;
while(i < n1 && j < n2)
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while(i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while(j < n2)
{
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
void mergeSort(int arr[], int left, int right)
{
if(left < right)
{
int mid = left + (right - left) / 2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}
}
void printArr(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%-5d",arr[i]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
mergeSort(arr,0,size - 1);
printArr(arr,size);
return 0;
}
6. 快速排序(Quick Sort)
快速排序是一种基于分治思想的高效排序算法。它通过选择一个基准值,将数组划分为两个部分:小于基准值的元素和大于基准值的元素,然后递归地对这两部分进行排序。
- 选择基准值:从数组中选择一个基准值(通常是第一个元素、最后一个元素或者任意元素)
- 分区:将数组重新排序,使所有小于基准值的元素位于基准值左侧,大于基准值的元素位于右侧
- 递归排序:对基准值两侧的子数组继续递归快速排序
- 重复上述步骤,直到有序
时间复杂度(平均): O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( l o g n ) O(logn) O(logn)(递归栈空间)
#include <stdio.h>
int partition(int arr[],int low,int high)
{
int pivot = arr[high];
int i = low -1;
for(int j = low; j < high; j++)
{
if(arr[j] <= pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSort(int arr[],int low,int high)
{
if(low < high)
{
int pi = partition(arr,low,high);
quickSort(arr,low,pi - 1);
quickSort(arr,pi+1,high);
}
}
void printArr(int arr[],int size)
{
for(int i = 0; i < size; i++)
printf("%-5d",arr[i]);
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
quickSort(arr,0,size-1);
printArr(arr,size);
return 0;
}
7. 堆排序(Heap Sort)
堆排序是一种基于堆结构的比较排序算法。堆是一颗完全二叉树,并且满足堆性质:
- 大顶堆:每个节点的值都大于或等于其左右子节点的值。
- 小顶堆:每个节点的值都小于或等于其左右子节点的值。
堆排序利用大顶堆的特性来实现升序排序(或小顶堆实现降序排序)(此处实现升序排序)
- 构建初始堆:将数组是为完全二叉树,并调整其为大顶堆。
- 交换堆顶和堆尾:堆顶元素是最大值,与最后一个元素交换,将最大值移到最终位置。
- 调整堆:交换后,重新调整为大顶堆。
- 重复步骤2、3。直到堆中只有一个元素
时间复杂度(平均): O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)
#include <stdio.h>
void heapify(int arr[],int n,int i)
{
int lastest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if(left < n && arr[left] > arr[lastest])
{
lastest = left;
}
if(right < n && arr[right] > arr[lastest])
{
lastest = right;
}
if(lastest != i)
{
int temp = arr[lastest];
arr[lastest] = arr[i];
arr[i] = temp;
heapify(arr,n,lastest);
}
}
void heapSort(int arr[],int n)
{
for(int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr,n,i);
}
for(int i = n - 1; i >= 0;)
{
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
i--;
heapify(arr,i,0);
}
}
void printArr(int arr[],int size)
{
for(int i = 0; i < size; i++)
{
printf("%-5d",arr[i]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {1,3,7,5,4,6,2,9,8};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
heapSort(arr,size);
printArr(arr,size);
return 0;
}
8. 计数排序(Counting Sort)
计数排序是一种非比较排序算法,适用于对整数或范围有限的离散数据进行排序。它通过统计每个元素出现的次数来确定元素在排序后的位置。它的核心思想是:
- 统计每个元素的出现次数
- 利用这些计数信息计算元素的位置索引
- 根据索引将元素放入正确的位置,从而完成排序
计算频率:
找到数组中最大值和最小值,确定数值范围
创建一个计数数组,记录每个值在原数组中出现次数
累积计数:
将计数数组转换为累积计数数组,表示每个值在排序后的位置范围
- 填充结果:
倒叙遍历原数组,根据累积计数数组将元素放到结果数组中,并更新计数数组
时间复杂度: O ( n + k ) O(n+k) O(n+k):n是数组大小,k是数据范围
空间复杂度: O ( n + k ) O(n+k) O(n+k):需要额外计数数组和结果数组
#include <stdio.h>
#include <stdlib.h>
void countSort(int arr[],int size)
{
int max = arr[0],min = arr[0];
for(int i = 0; i < size; i++)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
int len = max - min + 1;
int *count = (int *)calloc(len,sizeof(int));
for(int i = 0; i < size; i++)
{
count[arr[i]-min]++;
}
for(int i = 1; i < len; i++)
{
count[i] += count[i-1];
}
int *output = (int *)calloc(size,sizeof(int));
for(int i = size - 1; i >= 0; i--)
{
output[count[arr[i]-min]-1] = arr[i];
}
for(int i = 0; i < size; i++)
{
arr[i] = output[i];
}
free(count);
free(output);
}
void printArr(int arr[],int size)
{
for(int i = 0;i < size; i++)
printf("%-5d",arr[i]);
printf("\n");
}
int main(int argc,char *argv[])
{
int arr[] = {57, 31, 67, 89, 4, 12, 5, 54, 32, 63};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr,size);
countSort(arr,size);
printArr(arr,size);
return 0;
}
9. 桶排序(Bucket Sort)
桶排序是一种基于分布的排序算法,它通过将数据分配到多个桶中,然后分别对每个桶中的数据进行排序,最后合并所有桶中的数据来完成排序。适用于输入数据分布均匀的情况,特别是当数据范围有限且可以被分成多个区间时,效率较高。
- 分桶:根据数据范围,将数据分配到多个桶中,每个桶对应一个区间
- 桶内排序:对每个桶中的数据分别进行排序(推荐插入排序)
- 合并桶:依次合并每个桶中的数据
时间复杂度(平均): O ( n + k + n l o g ( n / k ) ) O(n+k+nlog(n/k)) O(n+k+nlog(n/k))
空间复杂度: O ( n + k ) O(n+k) O(n+k)
#include <stdio.h>
#include <stdlib.h>
// 链表节点
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 在链表中插入节点并保持排序顺序
void sortedInsert(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL || (*head)->data >= data) {
newNode->next = *head;
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 桶排序函数
void bucketSort(int arr[], int size) {
if (size <= 0) return;
// 找到数组中的最大值和最小值
int max = arr[0], min = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int bucketCount = 5; // 假设有5个桶
int range = (max - min + bucketCount) / bucketCount; // 每个桶存储的整数范围
Node** buckets = (Node**)malloc(bucketCount * sizeof(Node*));
for (int i = 0; i < bucketCount; i++) {
buckets[i] = NULL;
}
// 将元素分配到对应的桶
for (int i = 0; i < size; i++) {
int bucketIndex = (arr[i] - min) / range;
sortedInsert(&buckets[bucketIndex], arr[i]);
}
// 将桶内的元素合并回原数组
int index = 0;
for (int i = 0; i < bucketCount; i++) {
Node* current = buckets[i];
while (current != NULL) {
arr[index++] = current->data;
Node* temp = current;
current = current->next;
free(temp); // 释放链表节点
}
}
free(buckets); // 释放桶数组
}
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%-5d", arr[i]);
printf("\n");
}
int main() {
int arr[] = {21, 33, 17, 5, 44, 26, 32, 19, 38};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr, size);
bucketSort(arr, size);
printArr(arr, size);
return 0;
}
10.基数排序(Radix Sort)
基数排序是一种非比较排序算法,通过按位对数据进行多轮排序来实现。它是一种稳定的排序算法,适用于整数或字符串等离散数据的排序。基数排序的核心思想是将数据拆分为多个位,按照位的优先级(从低位到高位或从高位到低位)依次进行排序。
确定最大位数:找到数组中元素的最大数,决定排序的轮数
按位排序:
从最低为开始,对每一位进行排序
使用稳定的排序算法(如计数排序)对当前位上的数字进行排序
完成排序:
重复2,直到最高位
时间复杂度: O ( d ∗ ( n + k ) ) O(d*(n+k)) O(d∗(n+k)),其中d是位数,n是数据大小,k是基数
空间复杂度: O ( n + k ) O(n+k) O(n+k)
#include <stdio.h>
#include <stdlib.h>
// 使用计数排序对数组的某一位进行排序
void countSort(int arr[], int size, int exp) {
int output[size]; // 输出数组
int count[10] = {0}; // 计数数组
// 统计当前位数字的频率
for (int i = 0; i < size; i++) {
int digit = (arr[i] / exp) % 10;
count[digit]++;
}
// 计算累积频率
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 按当前位数字将元素放入输出数组
for (int i = size - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// 将排序结果复制回原数组
for (int i = 0; i < size; i++) {
arr[i] = output[i];
}
}
// 基数排序主函数
void radixSort(int arr[], int size) {
// 找到最大值,确定最高位
int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 从个位开始,对每一位进行排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countSort(arr, size, exp);
}
}
void printArr(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%-5d", arr[i]);
printf("\n");
}
int main() {
int arr[] = {1705, 43, 76, 90, 802, 24, 2, 66, 635};
int size = sizeof(arr) / sizeof(arr[0]);
printArr(arr, size);
radixSort(arr, size);
printArr(arr, size);
return 0;
}