10大排序算法（C语言实现）写在前面1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序8.计数排序9.桶排序10.基数排序

66 阅读 0 评论 44 点赞

我是靠谱客的博主完美服饰，最近开发中收集的这篇文章主要介绍10大排序算法（C语言实现）写在前面1.冒泡排序2.选择排序3.插入排序4.希尔排序5.归并排序6.快速排序7.堆排序8.计数排序9.桶排序10.基数排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

大一刚放寒假期间，回想一下马上进入大学时的心情，记得在暑假时加了一个学校acm战队的群，当时感觉很美好，想开学的时候努力一下进入校队的acm。可是自己又特别喜欢渗透，于是就把acm这个想法放下了，这几天把SQLlabs干完了，出于闲想看看算法。记得当时写C课设的时候，冒泡排序也把我整一段时间才迷糊过来。好，废话不多说，记录一下自己的学习成果。

写在前面

这些总结是根据菜鸟教程上的知识，加上自己的实验和思考的成果。十大经典排序算法.在这里我先说一下：下边所有的算法排序结果都从大到小

1.冒泡排序

算法思路：
这个算法了解过的非常好理解，大致说下就是：比较相邻数据，如果不符合规则（大的数在前或者小的数在前）就交换着两个数的位置。但是如果数据是：6，5，7（要求是大的数在前）根据上述所说的，得到的结果：6，7，5。这显然不符合要求，需要再经过一次循环才可得到正确的序列。因此冒泡排序的根本是：（如果要求序列是大的数在前）经过一次遍历循环后最小的数交换到整个数据的末尾。依次类推第二个小的数就在整个数据的倒数第二位，最后最大的数就在第一位。排序成功。

#include <stdio.h>
void bubble_sort(int arr[], int len)
{
int i, j, temp;
for (i = 0; i < len - 1; i++)
{
for (j = 0; j < len - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35};
int len = (int) sizeof(arr) / sizeof(*arr);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;
}

2.选择排序

算法思路：
假设第一个数据最大，遍历这个数据后边的所有数据，发现后边有数据大于这一个数据，记录较大的数据，继续往后遍历直到遍历一遍所有数据，之后交换数据，此时第一个数据即为整个数据的最大数。依次类推，假设第二个数据最大，遍历这个数据后边的所有数据，发现后边有数据大于这一个数据，记录较大的数据，继续往后遍历直到遍历一遍所有数据，之后交换数据。

#include<stdio.h>
int main()
{
int a[7]={6,3,7,5,9,10,2};
int i=0,j=0,max;
int temp,len=7;
for(i = 0;i<len;i++)
//判断i是否小于len，执行下面的语句
{
max = i;
//假设此次循环中的最大值就是当前的值
for(j = i+1;j<len;j++)
{
if(a[j]>a[max])
//将假设的当前最大值与后面的值比较
{
max = j;
//若后面的值更大，则交换下标
}
}//当前最大值
if(max != i)
//比较之后如果此次循环中最大值并非当前值
{
temp = a[i];
//将此次循环中的最大值与a[k]交换
a[i] = a[max];
a[max] = temp;
}
}
for(int q=0 ; q<7; q++)
printf("%d ",a[q]);
}

3.插入排序

算法思路：（为了具有普遍性，在此假设前3个数据已经过插入排序成为正序）
取出第四个数据，此时第四个数据的位置空出，如果第三个数据小于第四个数据，将第三个数据换到第四个数据的位置，此时第三个数据位置空出，如果仍小于，则以此类推。如果不小于则将取出的这个数据放到第三个数据的位置。

#include<stdio.h>
int main()
{
int arr[7]={6,3,7,5,9,10,2};
int i,j,key,len=7;
for(i=1;i<len;i++)
{
key = arr[i];//将数据取出来
j=i-1;
while((j>=0) && (arr[j]<key)) //如果不满足条件进入循环
{
arr[j+1] = arr[j];//移到前一个数据的位置，空出后一个数据的位置
j--;
}
arr[j+1] = key;
}
for(int q=0 ; q<7; q++)
printf("%d ",arr[q]);
}

4.希尔排序

#include<stdio.h>
int main()
{
int arr[7]={6,3,7,5,9,10,2};
int gap, i, j,len=7;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)
{
for (i = gap; i < len; i++)
{
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] < temp; j -= gap)
{
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
for(int q=0 ; q<7; q++)
printf("%d ",arr[q]);
}

5.归并排序

#include<stdio.h>
#include<stdlib.h>
int min(int x, int y)
{
return x < y ? x : y;
}
int main()
{
int arr[7]={6,3,7,5,9,10,2},len=7;
int *a = arr;
int *b = (int *) malloc(len * sizeof(int));
int seg, start;
for (seg = 1; seg < len; seg += seg) {
for (start = 0; start < len; start += seg * 2) {
int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int *temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
for(int q=0 ; q<7; q++)
printf("%d ",arr[q]);
}

6.快速排序

十大经典排序算法

7.堆排序

十大经典排序算法

8.计数排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void print_arr(int *arr, int n) {
int i;
printf("%d", arr[0]);
for (i = 1; i < n; i++)
printf(" %d", arr[i]);
printf("n");
}
void counting_sort(int *ini_arr, int *sorted_arr, int n) {
int *count_arr = (int *) malloc(sizeof(int) * 100);
int i, j, k;
for (k = 0; k < 100; k++)
count_arr[k] = 0;
for (i = 0; i < n; i++)
count_arr[ini_arr[i]]++;
for (k = 1; k < 100; k++)
count_arr[k] += count_arr[k - 1];
for (j = n; j > 0; j--)
sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
free(count_arr);
}
int main(int argc, char **argv) {
int n = 10;
int i;
int *arr = (int *) malloc(sizeof(int) * n);
int *sorted_arr = (int *) malloc(sizeof(int) * n);
srand(time(0));
for (i = 0; i < n; i++)
arr[i] = rand() % 100;
printf("ini_array: ");
print_arr(arr, n);
counting_sort(arr, sorted_arr, n);
printf("sorted_array: ");
print_arr(sorted_arr, n);
free(arr);
free(sorted_arr);
return 0;
}

9.桶排序

十大经典排序算法

10.基数排序

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10
void print(int *a, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%dt", a[i]);
}
}
void radixsort(int *a, int n) {
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i < n; i++) {
if (a[i] > m) {
m = a[i];
}
}
while (m / exp > 0) {
int bucket[BASE] = { 0 };
for (i = 0; i < n; i++) {
bucket[(a[i] / exp) % BASE]++;
}
for (i = 1; i < BASE; i++) {
bucket[i] += bucket[i - 1];
}
for (i = n - 1; i >= 0; i--) {
b[--bucket[(a[i] / exp) % BASE]] = a[i];
}
for (i = 0; i < n; i++) {
a[i] = b[i];
}
exp *= BASE;
#ifdef SHOWPASS
printf("nPASS
: ");
print(a, n);
#endif
}
}
int main() {
int arr[MAX];
int i, n;
printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;
printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("nARRAY
: ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("nSORTED : ");
print(&arr[0], n);
printf("n");
return 0;
}