关于排序的算法,大约分为两大类:顺序排序与对数排序。
顺序排序一般使用一对嵌套的循环结构(多为两个for循环),因此排序n个元素需要大约n的2次方的比较。比较常用的顺序排序有(1)选择排序法 (2)插入排序法 (3)冒泡排序法
对数排序一般需要大约n*log2n(2为底数)次比较。这两种排序,当n越大的时候,他们性能上的差别就越大。快速排序与归并排序都属于对数排序,同样是使用递归。
1)选择排序法
- public class Sort {
- // 选择排序
- public static void selectionSort(Comparable[] data) {
- int min;
- Comparable temp;
- // 从第一个元素开始比较,找出最小那个,放在第一位
- // 从第二个元素开始比较,找出最小那个,放在第二位
- // 总共需要放N-1次
- for (int index = 0; index < data.length - 1; index++) {
- min = index;
- for (int scan = index + 1; scan < data.length; scan++) {
- if (data[scan].compareTo(data[min]) < 0) {
- min = scan;
- }
- }
- //跳回到第一层循环的时候,才进行交换,把最小的数放在第一位...如此类推
- temp = data[min];
- data[min] = data[index];
- data[index] = temp;
- }
- }
- }
策略是:搜索整个数组,找到最小值。然后将这个值与第一个位置上的值交换。然后搜索除第一个值钱外的次小值,然后与第二个位置上的值进行交换。如此类推。这种算法最简单易明
2)插入排序
- // 插入排序
- public static void insertionSort(Comparable[] data) {
- // 插入一个数,与前面的数比较,放到适当的位置,如此类推
- for (int index = 1; index < data.length; index++) {
- Comparable temp = data[index];
- int position = index;
- while (position > 0 && data[position - 1].compareTo(temp) > 0) {
- data[position] = data[position - 1];
- position--;
- }
- data[position] = temp;
- }
- }
插入排序相对于选择排序要复杂一些,策略是:每插入一个数,与前面的所有数进行比较, 然后把这个数放到适当的位置。比如:数组里只有3,插入6,3与6排序后,插入4,然后4就放到第2位,之后插入5,3与4位置不变,5放在第3位,6换 到第4位...插入的过程需要移动数组的其他值,为插入的元素腾出存储空间。
3)冒泡算法
- public static void bubbleSort2(Comparable[] data) {
- Comparable temp;
- for (int i = 0; i < data.length; i++) {
- for (int j = 0; j < data.length - 1 - i; j++) {
- if (data[j].compareTo(data[j + 1]) > 0) {
- temp = data[j + 1];
- data[j + 1] = data[j];
- data[j] = temp;
- }
- }
- }
- }
冒泡算法大家应该最熟悉了...它的策略是:第一次对数组所有值进行比较,重复地比较相邻两个元素,比较后进行交换,把最大值移动到最后一个位置,然后再扫描除最后一位外的数组其他值,不断进行交换,把次大值移到倒数第2位,如此类推。每次比较都找出该次所有数中的最大值
上面3种顺序排序实现都很相似,效率也接近
现在看看如何使用递归实现排序
4)快速排序
- public static void quickSort(Comparable[] data, int min, int max) {
- int mid;
- if (min < max) {
- mid = findPartition(data, min, max);
- quickSort(data, min, mid - 1);
- quickSort(data, mid + 1, max);
- }
- }
- // quickSort的支撑方法
- private static int findPartition(Comparable[] data, int min, int max) {
- int left;
- int right;
- Comparable temp;
- Comparable partitionelement;
- // 以第一个元素为分割元素(不一定是data[min])
- partitionelement = data[min];
- left = min;
- right = max;
- while (left < right) {
- // 从左边找到比partitionelement大的数就跳出循环
- while (data[left].compareTo(partitionelement) <= 0 && left < right) {
- left++;
- }
- // 从右边找到比partitionelement小的数就跳出循环
- while (data[right].compareTo(partitionelement) > 0) {
- right--;
- }
- // 交换左边比partitionelement大的与右边比partitionelement小的元素
- if (left < right) {
- temp = data[left];
- data[left] = data[right];
- data[right] = temp;
- }
- }
- // 当left>=right的时候,交换分割元素与data[right]的位置(把分割元素放到去一个比较中间的位置)
- temp = data[min];
- data[min] = data[right];
- data[right] = temp;
- return right;
- }
策略:首先在数组中任意选择一个元素作为分割元素,上面的例子是选择第一个数。然后开 始分割数组,把比这个分割元素小的值都移到它的左边,比他大的都移到它的右边。然后递归调用这个方法,对左右两部分排序,类似地从左边选择一个分割元素, 把左边比它小的排在它的左边,比它大的排在它的有...然后到右边。直到只剩下一个元素时(即不能再分割时)完成排序。
这种排序需要3个参数,第一个为对象数组,第2个是数组索引的起始位置,第3个是数组索引的结束位置。
下面对这几种排序的实现和性能进行测试
- public static void main(String[] args) {
- long start = System.currentTimeMillis();
- Random rand = new Random();
- Integer array[] = new Integer[40000];
- for(int i=0;i<40000;i++){
- array[i] = rand.nextInt(10);
- }
- // 插入排序
- // insertionSort(array);
- // 选择排序
- // selectionSort(array);
- // 冒泡排序
- // bubbleSort(array);
- // 快速排序
- quickSort(array, 0, 39999);
- System.out.println(Arrays.toString(array));
- long end = System.currentTimeMillis();
- System.out.println("时间差:" + (end - start) + "毫秒");
- }
结论:
对有4万个(1~9)随机数的数组进行排序,在我的机器上运行,使用递归的快速查询约1秒,插入查询用5秒左右,选择查询11秒+,冒泡算法要几乎14秒。当然要查询的对象越少,他们之间效率的差别就越小。在排序对象的数量不多时,用顺序查询会比较方便与直观。
相关推荐
提供了Java实现几种常见排序方法和原理介绍
用Java实现几种常见的排序算法.txt
用Java实现几种常见的排序算法.txt
Java中几种比较常见的排序方法,像冒泡、快速排序、插入排序登。
Java实现几种常见的排序算法 ,共享一下
JAVA几种常用的经典的排序算法 冒泡 选择 快速 shell 堆排序
java 几种常用的排序算法 java 几种常用的排序算法
java排序算法,包括冒泡、插入、快速、选择等四种最常见的排序算法
Java几种常见的排序算法
几种常见排序算法JAVA实现.pdf
用Java实现几种常见的排序算法(经典收藏)
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
几种常见排序算法(JAVA实现).pdf
几种常见排序算法(Java实现),冒泡排序,快速排序,插入排序,选择排序