库函数（不讲武德法）
int cmp(const void *a, const void *b) {
return *(int*)a-*(int*)b;
}
调用qsort(nums,numsize,sizeof(int),cmp;
元素什么类型自己改一下就行了。
可以对a，b进行操作降序或者偶奇排序。
选择排序
void a(int *a,int n){
for(int i=0;i<n;++i){
int min=i;
for(int j=i+1;j<n;++j){
if(a[j]<a[min]){
min=j;
}
}
int c=a[min];
a[min]=a[i];
a[i]=c;
}
}
选择排序就是先选第一位为最小然后比较第一位，如果有小的就交换，依次比较第二位第三位...
冒泡排序
void a(int *a,int n){
for(int i=n-1;i>=0;--i){
for(int j=0;j<i;++j){
if(a[j]>a[j+1]){
int c=a[j+1];
a[j+1]=a[j];
a[j]=c;
}
}
}
}
把最大的元素冒泡到最右边。第一个和第二个大的在右边然后第二个和第三个.....直至最后一个。
插入排序
void a(int*a,int b){
for(int i=1;i<b;++i){
int c=a[i];
int j=i-1;
while(j>=0){
if(c<a[j]){
a[j+1]=a[j];
j--;
}else{
break;
}
}
a[j+1]=c;
}
}
第一个和第二个比较如果小于就覆盖交换，第三个再和第二个比较如果小就和第一个比较大了就插入，插入排序就是把元素和前面的比较如果大了就插入到比较元素的下一个位置，如果小了就把比较元素移到下一位。这个是我自己写的可能和书上的不太一样。
计数排序
void a(int *a,int n,int m){
int *b=(int *)malloc(sizeof(int)*(m+1));
memset(b,0,sizeof(int)*(m+1));
for(int i=0;i<n;++i){
b[a[i]]++;
}
int c=0;
for(int v=0;v<=m;++v){
while(b[v]>0){
a[c++]=v;
b[v]--;
}
}
free(b);
}
如果是负数要重新讨论排序，初始化数组长度为最大加一，把所有置为0，就是把最大元素找出来，如果目标数组有这一个数组就加一没有就下一个，然后把这个数组再赋值给原数组。知道最大值的话可以用这个。
归并排序
void merge(int* nums, int low, int mid, int high, int* arr){
int i, j, k;
for(k = low; k <= high; ++k)
arr[k] = nums[k];
for(i = low, j = mid+1, k = i; i <= mid && j <= high; ++k){
if(arr[i] <= arr[j])
nums[k] = arr[i++];
else
nums[k] = arr[j++];
}
while(i <= mid)
nums[k++] = arr[i++];
while(j <= high)
nums[k++] = arr[j++];
}
void mergeSort(int* nums, int low, int high, int* arr){
if(low < high){
int mid = (low + high) / 2;
mergeSort(nums, low, mid, arr);
mergeSort(nums, mid+1, high, arr);
merge(nums, low, mid, high, arr);
}
}
int* sortArray(int* nums, int numsSize, int* returnSize){
int* arr = (int*)malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
mergeSort(nums, 0, numsSize-1, arr);
return nums;
}
快速排序
int Partition(int* nums, int low, int high){
if(low < high){
int pivot = nums[low];
while(low < high){
while(low < high && nums[high] >= pivot)
--high;
nums[low] = nums[high];
while(low < high && nums[low] <= pivot)
++low;
nums[high] = nums[low];
}
nums[low] = pivot;
}
return low;
}
void QuickSort(int* nums, int low, int high){
if(low >= high)
return;
int pivotpos = Partition(nums, low, high);
QuickSort(nums, low, pivotpos-1);
QuickSort(nums, pivotpos+1, high);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
QuickSort(nums, 0, numsSize-1);
*returnSize = numsSize;
return nums;
}
快排应该是用的最多的。随便选一个元素小于他的放左边大的放右边然后再从左边到这个元素找一个元素当新的元素然后递归调用快排。
基数排序
void countingSort(int *array, int size, int exp) {
int *output = (int *)malloc(size * sizeof(int));
int count[10] = {0};
for (int i = 0; i < size; i++) {
count[(array[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = size - 1; i >= 0; i--) {
output[count[(array[i] / exp) % 10] - 1] = array[i];
count[(array[i] / exp) % 10]--;
}
for (int i = 0; i < size; i++) {
array[i] = output[i];
}
free(output);
}
void radixSort(int *array, int size) {
int max = array[0];
for (int i = 1; i < size; i++) {
if (array[i] > max) {
max = array[i];
}
}
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(array, size, exp);
}
}
按位数进行排序就是分类的。
桶排序
void bucketSort(float *array, int size) {
int BUCKET_SIZE = 10;
float **buckets = (float **)malloc(BUCKET_SIZE * sizeof(float *));
int *bucketSizes = (int *)calloc(BUCKET_SIZE, sizeof(int));
for (int i = 0; i < BUCKET_SIZE; i++) {
buckets[i] = (float *)malloc(size * sizeof(float));
}
for (int i = 0; i < size; i++) {
int bucketIndex = array[i] * BUCKET_SIZE;
buckets[bucketIndex][bucketSizes[bucketIndex]++] = array[i];
}
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucketSizes[i] > 0) {
qsort(buckets[i], bucketSizes[i], sizeof(float), (int (*)(const void *, const void *))compare);
}
}
int index = 0;
for (int i = 0; i < BUCKET_SIZE; i++) {
for (int j = 0; j < bucketSizes[i]; j++) {
array[index++] = buckets[i][j];
}
}
for (int i = 0; i < BUCKET_SIZE; i++) {
free(buckets[i]);
}
free(buckets);
free(bucketSizes);
}
int compare(const void *a, const void *b) {
return (*(float *)a - *(float *)b);
}
把所有元素放在几个桶里面排序，内存少可以用。
标签：nums,int,void,默认,high,++,low,升序,排序 From： https://blog.csdn.net/2303_78076382/article/details/141472427