从入门开始手把手搭建千万级Java算法测试-计数排序与快速排序的比较(常规快排)比较

  第九天开始呢，我们计数排序与快速排序的比较，从算法思路，到算法伪代码实现，到复杂度分析，从这里开始我们手把手搭建一个测试平台的基础，根据你自身硬件水平可以对下列代码进行从1000，到千万级测试，其中算法测试时间与你的机器硬件水平和实现的算法有关系，下面是计数排序与快速排序的比较具体讲解。
（1）排序算法的思路
  计数排序算法基本思路：max <-查找数组中的最大元素
用全零初始化计数数组， 对于j <-0到大小， 找到每个唯一元素的总数，然后 ， 将计数存储在count数组中的第j个索引处，对于我<-1到最大， 找到累积和并将其存储在count数组本身中，对于j <-减小到1，恢复元素到数组，最后将还原的每个元素的数量减少1，就得到最后需要的结果。

  快速排序基本思想：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到全部数据变成有序。
（2）算法伪代码

//计数排序
  counting_sort(A,k):
	C = [0 for i in range(k)]
	for num in A:
		C[num] = C[num] + 1
	for j in range(1,k):
		C[j] = C[j] + C[j-1]
	B = [0 for i in range(len(A))]
	A.reverse()
	for num in A:
		B[C[num]-1] = num
		C[num] = C[num]-1
	return B
//快排算法
   QuickSort(SeqList R,int low,int high){
		int pivotpos; 
		if(low<high){
			pivotpos = Partition(R,low,high); 
			QuickSort(R,low,pivotpos-1);
			QuickSort(R,pivotpos+1,high);
		}
	}

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（3）复杂度分析

1.时间复杂度：
最坏情况的复杂性： O(n+k)
最佳案例复杂度： O(n+k)
平均案件复杂度： O(n+k)
总体复杂度= O(max)+O(size)+O(max)+O(size)=O(max+size)
  在上述所有情况下，复杂度都是相同的，因为无论元素如何放置在数组中，算法都会经历n+k时间。
  任何元素之间都没有比较，因此它比基于比较的排序技术要好。但是，如果整数很大，那是不好的，因为应该制作该大小的数组。
2.空间复杂度：
  计数排序的空间复杂度为O(max)。元素范围越大，空间复杂度越大。

（4）代码主体部分

package runoob;
import java.util.Arrays;

public class CountSort {
    private static int FindMaxElement(Integer[] array) {//返回最大值
        int max = array[0];
        for (int val : array) {
            if (val > max)
                max = val;
        }
        return max;
    }

    private static int[] CountingSort(Integer[] array, int range) {//核心代码
        int[] output = new int[array.length];
        int[] count = new int[range];
        for (int i = 0; i < array.length; i++) {
            count[array[i]]++;
        }
        System.out.println("数据 " + Arrays.toString(count));

        for (int i = 1; i < range; i++) {
            count[i] = count[i] + count[i - 1];
        }
        System.out.println("数据和 " + Arrays.toString(count));

        for (int i = 0; i < array.length; i++) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }
        return output;
    }

    public static void CountSort_text(long num) {
        Quick_sort quick_sort=new Quick_sort();
        Integer[] arr = SortHelper.generateRandomArray(num, 0, 1000000);
        Integer[] arr2=Arrays.copyOfRange(arr,0, arr.length - 1);
        int max = FindMaxElement(arr);

        System.out.println("输入序列为");
        SortHelper.printArray(arr);
        long start = System.nanoTime();
        quick_sort.sort(arr, 0, arr.length - 1);
        long mid = System.nanoTime();
        final int[] ints = CountingSort(arr2, max + 1);
        long end = System.nanoTime();

        System.out.println("当前数据数量为"+num+"当前最大数据范围为"+max+"为了页面干净选择忽略打印排序结果");
        System.out.println("快速排序"+"花费时间:" + (mid - start)/1000 + "(ms)");
        System.out.println("计数排序"+"花费时间:" + (end - mid)/1000 + "(ms)");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

  对应代码中的SortHelper类我们留一个小小的悬念，留到最后来进行叙说，其中目前来说他的方法generateRandomArray的参数为，（num，left，right）第一个参数参与算法生成的数量级，作为随机生成序列，它可以为千万，因为是long级别，left和right则为生成序列的大小范围，生成的序列为返回值类型为Integer[]。
（5）测试结果如下：

  笔者有兴趣可以尝试千万级的算法测试，这里便不在赘述。