排序算法详解
1.快速排序
关于快速排序的逻辑原理是这样的：
将两个指针i，j分别指向表的起始和最后的位置，T为临时变量。
反复操作以下两步：
（1）j逐渐减小，并逐次比较j指向的元素和目标元素的大小，若p(j)<T则交换位置。
（2）i逐渐增大，并逐次比较i指向的元素和目标元素的大小，若p(i)>T则交换位置。
直到i，j指向同一个值，循环结束。
下面是源码
#include <stdio.h>
#include <stdlib.h>
void swap(int A[],int i,int j)
{
int temp=0;
if(A[i]>A[j])
{
temp=A[j];
A[j]=A[i];
A[i]=temp;
}
}
/* 快速排序 */
void quick_sort(int x[],int left, int right)
{
int temp = left;
int i;
if (left >= right)
return;
for (i = left+1; i<= right; i++)
{
if(x[i] < x[left])
swap(x, ++temp, i);
}
swap(x, left, temp);
quick_sort(x,left, temp-1);
quick_sort(x,temp+1, right);
}
int main()
{
int number[]={10,9,8,7,6,5,4,3,2,1};
int i=0,len;
printf("start ....\n");
len=(int)sizeof(number)/sizeof(*number);
printf("len =%d\n",len);
quick_sort(number,0,9);
for(i=0;i<10;i++)
{
printf("%d ",number[i] );
}
printf("\n");
printf("end ....\n");
exit(0);
}代码已经编译调试过了，亲测可行。
2.插入排序
#include <stdlib.h>
#include <stdio.h>
void printf_buf(int* buf, int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", buf[i]);
printf("\r\n");
}
void insert_funs(int *buf, int size)
{
int cur;
int i,j;
for (i = 1; i < size; i++)
{
printf(" %d poll:\r\n",i);
cur = buf[i];
for (j = i - 1; j >= 0 && buf[j] > cur; j --)
{
buf[j + 1] = buf[j];
}
buf[j + 1] = cur;
printf_buf(buf, size);
}
printf("\n");
}
int main(int argc, char* argv)
{
int num[] = { 14,3,12, 10, 12,1, 5 ,16};
int i;
printf("insert funs\r\n");
insert_funs(num, sizeof(num)/sizeof(num[0]));
printf("\n");
return 0;
}运行：
3.冒泡排序
#include<stdio.h>
#include<stdlib.h>
void printf_buf(int* buf, int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", buf[i]);
printf("\r\n");
}
void swap(int x[], int i, int j)
{
int temp = 0;
if (x[i] > x[j])
{
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
void BubbleSort(int a[], int len)
{
int i, j, temp;
for (j = 0; j < len - 1; j++)
{
for (i = 0; i < len - 1 - j; i++)
swap(a, i, i + 1);
}
}
int main()
{
int num[] = { 20, 8, 18, 3, 30, 14, 77, 32 };
int len = sizeof(num) / sizeof(num[0]);
int i = 0;
printf("start:\r\n");
printf_buf(num, len);
printf("\n");
BubbleSort(num, len);
printf("end:\r\n");
printf_buf(num, len);
printf("\n");
return 0;
}运行：
4.选择排序
原理：从所有记录中选出最小的一个数据元素与第一个位置的记录交换；然后在剩下的记录当中再找最小的与第二个位置的记录交换，循环到只剩下最后一个数据元素为止。
#include<stdio.h>
#include<stdlib.h>
void printf_buf(int* buf, int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", buf[i]);
printf("\r\n");
}
//如果下标为i的数大于下标为j的数，交互两个数的位置
void swap(int x[], int i, int j)
{
int temp = 0;
if (x[i] > x[j])
{
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
void selectSort(int num[], int size)
{
int i, j,minindex;
for (i; i < size; i++)
{
minindex = i;
for (j = i + 1; j < size; j++)
if (num[j] < num[minindex])
minindex = j;
swap(num, i, minindex);
}
}
int main()
{
int num[] = { 20, 8, 18, 3, 30, 14, 77, 32 };
int len = sizeof(num) / sizeof(num[0]);
int i = 0;
printf("start:\r\n");
printf_buf(num, len);
printf("\n");
selectSort(num, len);
printf("end:\r\n");
printf_buf(num, len);
printf("\n");
return 0;
}运行
5.希尔排序
希尔排序就是在一个序列中进行分组（简称：增量），然后对每个分组分别进行插入排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分成一组，算法便终止。
简单的说希尔排序是插入排序的升级版。
#include<stdio.h>
#include<stdlib.h>
void printf_buf(int* buf, int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", buf[i]);
printf("\r\n");
}
void shellSort(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
{
for (i = 0; i < gap; i++)
{
for (j = i + gap; j < n; j += gap)
{
if (a[j] < a[j-gap])
{
int tmp = a[j];//基数
int k = j - gap;//标记分组后的下标（j的前一个数据）
while (k >= 0 && a[k] > tmp)//前一个数大，就交换
{
a[k+gap] = a[k];
k -= gap;//查找前一个值
}
a[k + gap] = tmp;
printf_buf(a, n);
}
}
}
}
}
int main()
{
int num[] = { 8, 9, 1, 7, 2,3,5,4,6,0};
int len = sizeof(num) / sizeof(num[0]);
int i = 0;
printf("start:\r\n");
printf_buf(num, len);
printf("\n");
shellSort(num, len);
printf("end:\r\n");
printf_buf(num, len);
printf("\n");
return 0;
}
6.堆排序
7.归并排序
8.桶排序
9.计数排序
10.基数排序
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录