C++计数排序

1. 计数排序叫做CountingSort，而不是ChoiceSort

2. void ChoiceSort( int a[],int n )n表示数组元素个数，而while( k <n )k表示元素下标，下标和个数比较是不对的，应该改成while(k <n - 1)

3. for( i = 0 i <n i++ ),这样写会出现重复比贺脊饥较，如果当前元素是第3个，那么这段代码也从第一个元素开始比较，实际上前两个元素已经排好序列，所以改成for( i = k + 1 i <n i++ ),从当前元素的下一个开始比较

4. 一行代码只干一件事，不要把多个变量定义在同一行

5. 程序要模禅返块化一个函数只干一件事，不要即排序，又输出结果，把输出提取到外面

代码整理野碧后如下：

#include<iostream>

using namespace std

void CountingSort( int a[], int n )

{

int count = 0

int k = 0

while( k <n - 1)

{

for( int i = k + 1 i <n i++ )

{

if( a[k] >a[i] )

count++

}

if(count == 0)

k++

if( count >0 )

{

swap( a[k] , a[count] )

count = 0

}

}

}

void Output(int a[], int n)

{

for(int i = 0 i <n i++ )

cout <<a[i] <<" "

cout <<endl

}

int main()

{

int n = 5

int a[5] = { 4, 3, 1, 5, 2 }

CountingSort( a , 5 )

Output(a, 5)

system("pause")

return 0

}

这个程序还有点问题，

1. 动态数组申请

2. 访问越界

3. 输出错误

应该就这三个问题了吧，简单的调试了下。

1. 在第敬局9行出现，比较好解决。使用malloc内存分配函数直接解决，注意，在使用完成后需要用free（）去释放这段内存，否则会出现内存泄露。

2. 这个出现在第22行，判断条件写错了，应该判断是j，而不是i。可以将我改过的程序和原始程序进行比较。

3. 这个出现在第38行，因为这里对B数组进行修改，或者说排序，所以应该输出的B数组的元素。而原始程序是输出A数组的元素，这里A数组中的元素并没有改变，所以，输出肯定和定义A时一样，不会出现期望的顺序。

贴一下我执行的结果：

修改后的代码：

#include <stdio.h>

#include <string.h>

#include <malloc.h>

//计数排序函数

void counting_sort(int A[], int B[], int k, int length)     //k 为待排序数组A中最大元素

{

int i, j, temp

int *C = (int*)malloc(sizeof(int) * (k + 1))

for 咐稿埋(i = 0 i <= k i++)                        //数组C初始化 

{

C[i] = 0

}

for (j = 1 j <= length - 1 j++)                //C[i]中包含等于i的元素的个数 

{

C[A[j]] = C[A[j]] + 1

}

for (i = 1 i <= k i++)                        //C[i]中包含小于或等于i的元素的个数 

{

C[i] = C[i] + C[i - 1]

}

for 衡蚂(j = length - 1 j >= 0 j--)                //元素重排 

{

B[C[A[j]]] = A[j]

C[A[j]]--

}

free(C)

}

//测试计数排序函数

main()

{

int A[] = { 2, 6, 1, 2, 4, 5, 9, 6, 4, 5, 8, 2, 3, 7 }

int B[] = { 2, 6, 1, 2, 4, 5, 9, 6, 4, 5, 8, 2, 3, 7 }

int k = 9, i

counting_sort(A, B, 9, 14)

for (i = 0 i <= 13 i++)

printf("    %d", B[i])

printf("\n")

return 0

}

方法步御瞎骤如下：

1．首先，定义一个结构，包塌拆散括数值、排名和序号。

2．定义结构数组变量d，保存所有整数信息。

3．接下来，定义一个自定义函数来比较整数序列中任意两个整数的大小。

4．定义一个自定义函数，比较整数序列中任意两个数字的序数大小。

5．在主函数中，首先定义两个整数，并保存整数个数和排名计数。

6．使用for循环输入序列中的整数，并设置序列中每个整数的序列号。

7．按整数大小排序的序列中的所有数值。

8．将好排序数值添加排序编号。

9．最后，根据索引输出所有整数的排序。

注意：

（1）交换排序：团氏参照求最大值和最小值的思想，按升序排序的基本过程是将第一个数字与下一个数字进行比较。如果后面的数字很小，那么交换和第一个数字的位置。否则，不要交换。

（2）气泡排序：交换和重复两个相邻数字的过程。一般来说，如果有n个数字要排序，则需要n－1起泡。

（3）选择排序：在交换顺序的基础上，找出剩余数量的最大值，并与地面上的I＋1数量进行交换，使得每轮比较中只有一次交换 *** 作，该算法最多只有n－1个交换 *** 作。

---