c语言实现简单排序(8种方法)

#include

#include

//冒泡排序

voidbubleSort(int data[], int n);

//快速排序

voidquickSort(int data[], int low, int high);

intfindPos(int data[], int low, int high);

//插入排序

voidbInsertSort(int data[], int n);

//希尔排序

voidshellSort(int data[], int n);

//选择排序

voidselectSort(int data[], int n);

//堆排序

voidheapSort(int data[], int n);

void swap(int data[], inti, int j);

voidheapAdjust(int data[], inti, int n);

//归并排序

voidmergeSort(int data[], int first, int last);

void merge(int data[], int low, int mid, int high);

//基数排序

voidradixSort(int data[], int n);

intgetNumPos(intnum, intpos);

int main() {

int data[10] = {43, 65, 4, 23, 6, 98, 2, 65, 7, 79};

inti;

printf("原先数组:");

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

/*printf("冒泡排序:");

bubleSort(data, 10);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

printf("快速排序:");

quickSort(data, 0, 9);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

printf("插入排序:");

bInsertSort(data,10);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

printf("希尔排序:");

shellSort(data, 10);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

printf("选择排序:");

selectSort(data, 10);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};

inti;

printf("原先数组:");

int data[11] = {-1, 43, 65, 4, 23, 6, 98, 2, 65, 7, 79};

for(i=1;i<11;i++) {

printf("%d ", data[i]);

}

printf("n");

printf(" 堆排序:");

heapSort(data, 10);

for(i=1;i<11;i++) {

printf("%d ", data[i]);

}

printf("n");

printf("归并排序:");

mergeSort(data, 0, 9);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");*/

printf("基数排序:");

radixSort(data, 10);

for(i=0;i<10;i++) {

printf("%d ", data[i]);

}

printf("n");

return 0;

}

/*--------------------冒泡排序---------------------*/

voidbubleSort(int data[], int n) {

inti,j,temp;

//两个for循环，每次取出一个元素跟数组的其他元素比较

//将最大的元素排到最后。

for(j=0;j

//外循环一次，就排好一个数，并放在后面，

//所以比较前面n-j-1个元素即可

for(i=0;i

if(data[i]>data[i+1]) {

temp = data[i];

data[i] = data[i+1];

data[i+1] = temp;

}

}

}

}

/*--------------------快速排序---------------------*/

intfindPos(int data[], int low, int high) {

//将大于t的元素赶到t的左边，大于t的元素赶到t的右边

int t = data[low];

while(low < high) {

while(low < high && data[high] >= t) {

high--;

}

data[low] = data[high];

while(low < high && data[low] <=t) {

low++;

}

data[high] = data[low];

}

data[low] = t;

//返回此时t在数组中的位置

return low;

}

//在数组中找一个元素，对大于该元素和小于该元素的两个数组进行再排序

//再对两个数组分为4个数组，再排序，直到最后每组只剩下一个元素为止

voidquickSort(int data[], int low, int high) {

if(low > high) {

return;

}

intpos = findPos(data, low, high);

quickSort(data, low, pos-1);

quickSort(data, pos+1, high);

}

/*--------------------插入排序---------------------*/

voidbInsertSort(int data[], int n) {

intlow,high,mid;

inttemp,i,j;

for(i=1;i

low = 0;

//把data[i]元素插入到它的前面data[0-(i-1)]中

temp =data[i];

high = i-1;

//该while是折半，缩小data[i]的范围(优化手段)

while(low <= high) {

mid = (low+high)/2;

if(data[mid] > temp) {

high = mid-1;

}

else {

low = mid+1;

}

}

int j = i;

//让data与已经排序好的数组的各个元素比较，小的放前面

while((j > low) && data[j-1] > temp) {

data[j] = data[j-1];

--j;

}

data[low] = temp;

}

}

/*--------------------希尔排序---------------------*/

voidshellSort(int * data, int n) {

intstep,i,j,key;

//将数组按照step分组，不断二分到每组只剩下一个元素

for(step=n/2;step>0;step/=2) {

//将每组中的元素排序，小的在前

for(i=step;i

key = data[i];

for(j=i-step;j>=0 && key

data[j+step] = data[j];

}

//和上面的for循环一起，将组中小的元素换到数组的前面

data[j+step] = key;

}

}

}

/*--------------------选择排序---------------------*/

voidselectSort(int data[], int n) {

inti,j,mix,temp;

//每次循环数组，找出最小的元素，放在前面，前面的即为排序好的

for(i=0;i

//假设最小元素的下标

int mix = i;

//将上面假设的最小元素与数组比较，交换出最小的元素的下标

for(j=i+1;j

if(data[j] < data[mix]) {

mix = j;

}

}

//若数组中真的有比假设的元素还小，就交换

if(i != mix) {

temp = data[i];

data[i] = data[mix];

data[mix] = temp;

}

}

}

/*--------------------堆排序---------------------*/

//堆排序将数组先组成二叉树，默认从数组的data[1]开始排，data[0]是

//无效数据

voidheapSort(int data[], int n) {

inti;

//先将数组组成一棵完全二叉树

//从2/n开始，就是从倒数第二排结点往前开始

for(i=n/2;i>0;i--) {

heapAdjust(data, i, n);

}

//循环每个结点，将大的结点交换到堆顶

for(i=n;i>1;i--) {

swap(data, 1, i);

//每次交换完都要调整二叉树，将剩下的最大的结点交换到堆顶

heapAdjust(data, 1, i-1);

}

}

//交换函数

void swap(int data[], inti, int j) {

int temp;

temp = data[i];

data[i] = data[j];

data[j] = temp;

}

voidheapAdjust(int data[], inti, int n) {

int j, temp;

//假设第一个结点的元素是最大的

temp = data[i];

//i结点：2*i是i结点的左结点，2*i+1是i结点的右结点

//把结点元素大的交换到前面

for(j=2*i;j<=n;j*=2) {

if(j < n && data[j] < data[j+1]) {

j++;

}

if(temp >= data[j]) {

break;

}

data[i] = data[j];

i = j;

}

data[i] = temp;

}

/*--------------------归并排序---------------------*/

voidmergeSort(int data[], int first, int last) {

int mid = 0;

//将数组不停的二分分组再组合，直到每组只剩一个元素

if(first < last) {

mid = (first+last)/2;

mergeSort(data, first, mid);

mergeSort(data, mid+1, last);

merge(data, first, mid, last);

}

return;

}

void merge(int data[], int low, int mid, int high) {

inti, k;

//定义一个临时数组存放传进来的无序数组排好序之后的数组

int *temp = (int *)malloc((high-low+1)*sizeof(int));

//将无序数组分成两个序列

intleft_low = low;

intleft_high = mid;

intright_low = mid+1;

intright_high = high;

//将两个序列比较排序，小的排前

for(k=0;left_low<=left_high&&right_low<=right_high;k++) {

if(data[left_low]<=data[right_low]) {

temp[k] = data[left_low++];

}

else{

temp[k] = data[right_low++];

}

}

//左序列如果有剩下元素未排序，加到临时数组的末尾

if(left_low<= left_high) {

for(i=left_low;i<=left_high;i++) {

temp[k++] = data[i];

}

}

//右序列如果有剩下元素未排序，加到临时数组的末尾

if(right_low<= right_high) {

for(i=right_low;i<=right_high;i++) {

temp[k++] = data[i];

}

}

//将排好序的小分组转移到原数组中

for(i=0;i

data[low+i] = temp[i];

}

free(temp);

return;

}

/*--------------------基数排序---------------------*/

//该函数的作用是找出num的pos位数的数字(比如：23的个位数数字是3)

intgetNumPos(intnum, intpos) {

inti;

int temp = 1;

for(i=0;i

temp *= 10;

}

return (num / temp) % 10;

}

voidradixSort(int data[], int n) {

inti,j,k,pos,num,index;

//这几句话是创建一个从0-9(行)× (n+1)(列)的网格，第一列从上往下是0-9,

//第二列是该行包含的元素个数，默认为0个

int *radixArrays[10];

for(i=0;i<10;i++) {

radixArrays[i] = (int *)malloc(sizeof(int) * (n+1));

radixArrays[i][0] = 0;

}

//pos最大为31为数，计算机能承受的最大范围了

for(pos=1;pos<=31;pos++) {

//该for循环是将数组的元素按照位数(pos)的值放进网格内

for(i=0;i

num = getNumPos(data[i], pos);

index = ++radixArrays[num][0];

radixArrays[num][index] = data[i];

}

//该for循环是将上面的for循环已经按照某个位数(pos)排列好的元素存入数组

for(i=0,j=0;i<10;i++) {

for(k=1;k<=radixArrays[i][0];k++) {

data[j++] = radixArrays[i][k];

}

//清空网格，以便给下个位数排列

radixArrays[i][0] = 0;

}

}

}

以上排序算法的优劣（时间复杂度和空间复杂度对比）：