首页 > 代码库 > 基于非比较的排序：计数排序（countSort），桶排序（bucketSort），基数排序（radixSort）

基于非比较的排序：计数排序（countSort），桶排序（bucketSort），基数排序（radixSort）

2024-07-02 18:55:27   223人阅读

计数排序

条件：要排序的数组的元素必须是在一定范围的，比如是1~100。在排序之前我们必须知道数组元素的范围。
思路：顾名思义：就是用一个数组来计数的。
步骤：
1、用一个数组来计数count[ ],将要排序的数组arr[ ]的元素记为数组count[ ]数组的下标，如果数组arr[]中有两个数相同就在count[]++.如count[arr[i]]++.
2、 再一次遍历数组count[ ],将count[i]  +=  count[i-1]+count[i-2]+....+count[0],为的是记录该下标对应的元素在数组中的位置。
3、开始进行排序，我们用一个数组来记录排好序的元素sorted[ ]。
4、由步骤2我们可以清楚的知道count[ ]中下标对应的的元素在所有元素的排位（即排到第几个数）。但是必须减一（因为比如排到第五位对应的数组下标应该是4）。
5、具体的表达式为：
count[arr[i ] ]--;//就是在sorted[]中下标减一
sorted[ count[arr[i ] ] ]  = a[ i ];//count[ arr[ i] ]在sorted[ ]中对应的位置，等于a[ i ]就是对应元素的值。
6、按步骤5的方式遍历完数组的长度就能得到排序好的数组sorted[].
时间复杂度：O（N + K）
代码：show you my code!
public class CountSort {
	static int[] countSort(int[] a, int range/*数组元素的范围*/){
		int count[] = new int[range];
		for (int i = 0; i < a.length; i++) {
			count[a[i]]++;
		}
		for (int i = 1; i < count.length; i++) {
			count[i] += count[i-1];
		}
		int sortArr[] = new int[a.length];
		for (int i = 0; i < sortArr.length; i++) {
			count[a[i]]--;
			sortArr[count[a[i]]] = a[i];
		}
		return sortArr;
	}
	
	public static void main(String[] args) {
		int[] a = {1,34,66,90,99,34,56,2,3,47,66,99};
		
		int[] sortArr = countSort(a,100);
		for (int i = 0; i < sortArr.length; i++) {
			System.out.print(sortArr[i]+" ");
		}
	}
}

桶排序

条件：类似于计数排序，必须知道要排序的元素的范围（如0~N）。
思路：
1、我们可以把根据元素的范围将范围分成K个范围（每个范围对应一个桶）（K=N/常数）。
2、接着我们可以对将要排序的数组元素分派到对应的桶中。
3、我们再对各个桶进行排序（用插入排序）。（如果每个桶的数据都是一样的或者是桶的范围为1，此时就退化成计数排序）。
4、排好后的各个桶的排列就是排好序的。
时间复杂度为：O（N +Ｋ），最坏为（N^2）就是全部都在一个桶里（对桶进行插入排序时间复杂度就是为N^2）,空间复杂度为（N*K）。
适用：适用于大数据排序，牛逼闪闪，哈哈！
CODE：参考自点击打开链接。
#include <time.h>
#include <iostream>
#include <iomanip>
using namespace  std;

/*initial arr*/
void InitialArr(double *arr,int n)
{
	srand((unsigned)time(NULL));
	for (int i = 0; i<n;i++)
	{
arr[i] = rand()/double(RAND_MAX+1);   //(0.1)
}
}

/* print arr*/
void PrintArr(double *arr,int n)
{
	for (int i = 0;i < n; i++)
	{
		cout<<setw(15)<<arr[i];
		if ((i+1)%5 == 0 || i ==  n-1)
		{
			cout<<endl;
		}
	}
}

void BucketSort(double * arr,int n)     
{
	double **bucket = new double*[10];
	for (int i = 0;i<10;i++)
	{
		bucket[i] = new double[n];
	}
	int count[10] = {0};
	for (int i = 0 ; i < n ; i++)
	{
		double temp = arr[i];
int flag = (int)(arr[i]*10); //flag标识小树的第一位 
bucket[flag][count[flag]] = temp; //用二维数组的每个向量来存放小树第一位相同的数据
int j = count[flag]++;

/* 利用插入排序对每一行进行排序 */
for(;j > 0 && temp < bucket[flag][j - 1]; --j)
{
	bucket[flag][j] = bucket[flag][j-1];
}
bucket[flag][j] =temp;
}

/* 所有数据重新链接 */
int k=0;
for (int i = 0 ; i < 10 ; i++)
{
	for (int j = 0 ; j< count[i];j++)
	{
		arr[k] = bucket[i][j];
		k++;
	}
}
for (int i = 0 ; i<10 ;i++)
{
	delete bucket[i];
	bucket[i] =NULL;
}
delete []bucket;
bucket = NULL;
}

void main()
{
	double *arr=new double[10];
	InitialArr(arr, 10);
	BucketSort(arr, 10);
	PrintArr(arr,10);
	delete [] arr;
}



基数排序
条件相对比较宽松：可以使比较无规律的范围，但是尽量不要参进来负数，不然就得另作考虑。
思路：
1、我们可以每次取各元素的一个位来进行比较从各位到最大的位依次进行比较。这样最终就能得到已排好序的元素。
2、如：现在有一下元素：9, 23，34, 78，345.
A：对个位进行排序：23， 34， 345， 78， 9.
B：对十位进行排序：9(注：9的十位是0), 23, 34, 345,78.
C：对百位进行排序：9， 23， 34， 78， 345.
3、每次进行的排序用的是计数排序。
时间复杂度：O（K*N）
CODE：维基百科：基数排序
#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("%d\t", 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;
}































        

            
                
                  
                
                

                    联系

                    我们