#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//数组的首地址传进去
void bubbleSorting(int *arr,int arrLength){
for (int i = 0; i < arrLength; ++i) {
for (int j = 0; j < arrLength-i-1; ++j) {
if(arr[j]>arr[j+1]){
int temp = arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
int main(){
int arr[]={3,9,-1,10,20};
int length = sizeof(arr)/sizeof(int);
printf("%d\n",length);
bubbleSorting(arr,length);
for (int i = 0; i < length; ++i) {
printf("%d ",arr[i]);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void selectedSorting(int* arr,int length){
//int minNum = INT_MAX; //整数中的最小值,由于是局部变量，必须赋初值
for (int i = 0; i < length; ++i) {
int minNum = INT_MAX; //整数中的最小值,由于是局部变量，必须赋初值
int index = 0;
for (int j = i; j < length; ++j) {
if(arr[j]<minNum){
minNum=arr[j];
index = j;
}
}
//交换位置
arr[index]=arr[i];
arr[i]=minNum;
}
}
int main() {
int arr[]={8,3,2,1,7,4,6,5};
selectedSorting(arr, sizeof(arr)/ sizeof(int));
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void insertionSorting(int* arr,int length){
for (int i = 1; i < length; ++i) {
//首先获取当前元素和索引
int currentNum = arr[i];
int currentIndex = i;
while (currentNum<arr[currentIndex-1] && currentIndex>=0){
arr[currentIndex]=arr[currentIndex-1];
currentIndex--;
}
arr[currentIndex]=currentNum;
}
}
int main() {
int arr[]={8,3,2,1,7,4,6,5};
insertionSorting(arr, sizeof(arr)/ sizeof(int));
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
printf("hello,world!");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void shellSorting(int* arr,int length){
for (int gap = length/2; gap >=1 ; gap=gap/2) {
for (int i = 0; i < length; i=i+gap) {
int currentNum = arr[i];
int currentIndex = i;
while (currentNum<arr[currentIndex-gap] && currentIndex>=0){
arr[currentIndex]=arr[currentIndex-gap];
currentIndex=currentIndex-gap;
}
arr[currentIndex]=currentNum;
}
}
}
int main() {
int arr[]={8,3,2,1,7,4,6,5};
shellSorting(arr, sizeof(arr)/ sizeof(int));
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
printf("hello,world!");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//递归形式进行排序，分程左右两个部分，需要找到一个基准数
void quickSorting(int *arr,int left,int right){
int l = left;
int r = right;
//pivot 中轴值
int pivot = arr[(right+left)/2];
int temp = 0;
// while循环的目的是比中轴值小放到左边， 比中轴值大放到右边
while (l<r){
//左边先找,找到一个元素
while (arr[l]<pivot){
l+=1;
}
//右边先找,找到一个元素
while (arr[r]>pivot){
r-=1;
}
//如果l>=r说明pivot的左右两的值，已经交完完成
if(l>=r){
break;
}
//交换
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
//如果交换完后，发现这个arr[l]==pivot值 相等r--,前移
if(arr[l]==pivot){
r-=1;
}
//如果交换完后，发现这个arr[r]==pivot值 相等l++,前移
if(arr[r]==pivot){
l+=1;
}
}
//如果l==r，必须l++ ,r-- ，否则为出现栈溢出
//如果是奇数个数字，如果不再走一步，就会在中间相遇，必须错开中轴值
if(l==r){
l+=1;
r-=1;
}
//向左递归
if(left<r){
quickSorting(arr,left,r);
}
//向右递归
if(right>l){
quickSorting(arr,l,right);
}
}
int main() {
int arr[]={8,3,2,1,7,4,6,5};
quickSorting(arr, 0,(sizeof(arr)/ sizeof(int))-1);
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
printf("hello,world!");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//合并数组
void merge(int* arr,int left,int mid,int right,int *temp){
int i = left; //初始化i，左边有序序列的初始索引
int j = mid+1; //初始化j，右边有序序列的初始索引
int t = 0; //指向temp数组的当前索引
//第一步
//先把左右两边（有序）的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t]=arr[i];
t+=1;
i+=1;
}else{
temp[t]=arr[j];
t+=1;
j+=1;
}
}
//第二步
//把剩余数据的一边的数据依次全部填充到temp中
while (i<=mid){
temp[t]=arr[i];
t+=1;
i+=1;
}
while (j<=right){
temp[t]=arr[j];
t+=1;
j+=1;
}
//第三步
//将temp数据拷贝到arr
//注意，并不是每次都拷贝所有
t=0;
int tempLeft =left;
while (tempLeft<=right){
arr[tempLeft]=temp[t];
t+=1;
tempLeft+=1;
}
}
/**
* @param arr 待排序的数组
* @param left 左索引
* @param right 右索引
* @param temp 临时开辟的数组，用于局部排序和存储
*/
void mergeSorting(int* arr,int left,int right,int *temp){
if(left<right){
int mid = (left+right)/2; //中间索引
//向左递归拆解
mergeSorting(arr,left,mid,temp);
//向右递归拆解
mergeSorting(arr,mid+1,right,temp);
//聚合
merge(arr,left,mid,right,temp);
}
}
int main() {
int arr[]={8,3,2,1,7,4,6,5};
int temp[sizeof(arr)/ sizeof(int)]={};
mergeSorting(arr, 0,sizeof(arr)/ sizeof(int),temp);
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
printf("hello,world!");
return 0;
}
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成后，数列就变成了一个有序序列。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#define NUMBER 10
void radixSorting(int *arr, int length) {
char strTemp[] = " ";
int max = arr[0];
for (int i = 0; i < length; ++i) {
if (arr[i] >= max) {
max = arr[i];
}
}
//得到最大数的是几位数
sprintf(strTemp,"%d",max);
int maxLength = strlen(strTemp);
//定义一个二维数组，表示10个桶，每个桶就是一个一维数组
//二维数组包括10个一维数组
int bucket[10][length];
//为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录每个桶每次放入的数据的个数
//即bucketElementCounts[0] 代表bucket[0]中存放的个数
int bucketElementCounts[10]={};
for (int i = 0,n=1; i < maxLength; ++i,n*=10) {
//针对每个元素的对应位进行排序处理，第一次是各位，第二次是十位，第三次是百位
for (int j = 0; j < length; ++j) {
//取出每个元素对应位的值
int digitOfElement = arr[j]/n%10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
int index =0;
//遍历每一桶，并将桶中得数据，放回到原数组
for (int k = 0; k < sizeof(bucketElementCounts)/ sizeof(int); ++k) {
//如果桶中有数据，我们才放回到原数组中
if(bucketElementCounts[k]!=0){
//循环该桶，即第k个桶（即第k个一维数组），放入
for (int l = 0; l < bucketElementCounts[k]; ++l) {
//取出元素放回到arr
arr[index++]=bucket[k][l];
}
}
//取出数据放回后，需要将记录每个桶的中元素个数的数据清零
bucketElementCounts[k]=0;
}
}
}
int main() {
int arr[] = {53, 3, 542, 748, 14, 214};
radixSorting(arr, sizeof(arr)/ sizeof(int));
for (int i = 0; i < sizeof(arr)/ sizeof(int); ++i) {
printf("%d ",arr[i]);
}
return 0;
}
速度较快，但是遇到超大数量级的就不行了。空间不足，容易造成内存溢出。