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

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

2024-07-07 17:56:33   226人阅读

计数排序

条件：要排序的数组的元素必须是在一定范围的，比方是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;
}































        

            
                
                  
                
                

                    联系

                    我们