当前位置:   article > 正文

最新十大排序算法详细讲解,以及各种应用场景_十大算法及其应用场景

十大算法及其应用场景


**

十大排序算法汇总

**
在这里插入图片描述

比较和非比较的区别

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。
冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。
比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr之前有多少个元素,则唯一确定了arr在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

一些基本的术语

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面,而a=b,排序之后a可能出现在b的后面;
内排序:所有的排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
时间复杂度:一个算法执行所消耗的时间;
空间复杂度:运行完一个程序所需内存的大小。

排序算法复杂度及稳定性

在这里插入图片描述

一、冒泡排序

算法简介

1.从左向右依次对比相邻元素,将较大值交换到右边;
2.每一轮循环可将最大值交换到最左边
3.重复1.2两个步骤,直至完成整个数组。

动图演示

在这里插入图片描述

代码实现

/**
	 * 冒泡算法的实现
	 * @param array
	 * @return
	 */
	public static int[] bubbleSort(int[] array) {
		if(array.length==0) {
			return array;
		}
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length-1-i; j++) {
				if(array[j+1]<array[j]) {
					int temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
				}
			}
		}
		return array;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

应用场景

一般在学习的时候作为理解排序原理的时候使用,在实际应用中不会使用

算法分析

最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

二、快速排序

算法简介

1.选择一个元素赋值给中间元素temp,默认选择左边第一个元素,这样左边第一个元素的位置就空出来了;
2. 先从最右边的元素开始依次跟temp比较大小,大于等于temp元素的原地不动,遇到小于temp元素的则终止循环,把该元素赋值到左侧空出来的位置,同时左侧索引值自增,这是该元素原来的位置就空出;
3. 然后左侧元素开始依次跟temp比较大小,小于等于temp元素的原地不动,遇到大雨temp元素的则终止循环,把该元素赋值到右侧空出来的位置,同时右侧索引值自减;
4. 依次循环2,3步,直至左侧索引等于右侧索引,则完成一轮循环,把哨兵赋值到该索引的位置。
5. 在分别递归地对temp左右两侧的子数组进行1234步,直至递归子数组只有一个元素则排序完成

动图演示

在这里插入图片描述

代码实现

package leetcode;
/**
 * 快速排序算法
 * @author acer
 *
 */
public class Quick_sort {
	public void quicksort(int[] n, int left, int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp - 1);
            quicksort(n, dp + 1, right);
        }
    }
    public int partition(int[] n, int left, int right) {
        int pivot = n[left];//选择第一个为参考点
        while (left < right) {
            while (left < right && n[right] >= pivot)//让参考点与最右边的相比较,小于不动,大于右面减一
                right--;
            if (left < right)//让小于参考点的数,进入空出来的位置,
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)//让参考点与左边的相比较,小于左面加一,大于不动
                left++;
            if (left < right)//让大于参考点的数,进入空出来的位置
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }
    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,47};
        Quick_sort sort=new Quick_sort();
        sort.quicksort(a, 0, a.length-1);
        for(int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }

}

  • 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

超级详细解析

算法分析

最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn)

三、简单插入排序

算法简介

1.左边第一个元素可作为有序子数组;
2.从第二个元素开始,依次向前比较,大于该元素的则向右移一位,直到比该元素小的元素,插入其后;
3.依次向后推进,直至整个数组成为有序数组

动图演示

在这里插入图片描述

代码实现

package leetcode;

public class Insert_sort {
	public static void main(String[] args) {
		int[]  array= {3,3,345,2,753,4765,734658,567};
		int[] arrayNew=Insert_sort.insert_sort(array);
		for (int i = 0; i < arrayNew.length; i++) {
			System.out.print(arrayNew[i]+"     ");
		}
	}
	public static int[] insert_sort(int[] array) {
		if(array.length==0) {
			return array;
		}
		int current;
		for (int i = 0; i < array.length-1; i++) {
			current=array[i+1];
			int preIndex=i;
			while(preIndex>=0&&current<array[preIndex]) {
				array[preIndex+1]=array[preIndex];
				preIndex--;
			}
			array[preIndex+1]=current;
		}
		return array;
	}
}

  • 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

应用场景

如果大部分数据距离它正确的位置很近或者近乎有序?例如银行的业务完成的时间
如果是这样的话,插入排序是更好的选择。

算法分析

最佳情况:T(n) = O(n) 最坏情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

四、希尔排序

希尔排序的具体实现

算法简介

1.首先选择一个步长值gap,以步长值为间隔把数组分为gap个子数组gap=length/2
2.对每个子数组进行插入排序;
3.逐步减小步长 gap = gap/2,重复对数组进行1,2 步骤;
4.当步长值减为1时,相当于对数组进行一次直接插入排序。

图片演示

在这里插入图片描述

代码实现

package leetcode;

public class Shell_sort {
	
	public static void main(String[] args) {
		int[]  array= {3,3,345,2,753,4765,734658,567,7};
		int[] arrayNew=Shell_sort.shell_sort(array);
		for (int i = 0; i < arrayNew.length; i++) {
			System.out.print(arrayNew[i]+"     ");
		}
	}
	public static int[] shell_sort(int[] array) {
		if(array.length==0) {
			return array;
		}
		int length=array.length;
		int temp,gap=length/2;
		while(gap>0) {
			for (int i = gap; i < length; i++) {
				temp=array[i];
				int preIndex=i-gap;
				while(preIndex>=0&&array[preIndex]>temp) {
					array[preIndex+gap]=array[preIndex];
					preIndex-=gap;
				}
				array[preIndex+gap]=temp;
			}
			gap/=2;
		}
		return array;
	}
}

  • 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

算法的优点

相对于直接插入排序,希尔排序要高效很多,因为当gap 值较大时,对子数组进行插入排序时要移动的元素很少,元素移动的距离很大,这样效率很高;在gap逐渐减小过程中,数组中元素已逐渐接近排序的状态,所以需要移动的元素逐渐减少;当gap为1时,相当于进行一次直接插入排序,但是各元素已接近排序状态,需要移动的元素很少且移动的距离都很小。

算法分析

最佳情况:T(n) = O(nlog2 n) 最坏情况:T(n) = O(nlog2 n) 平均情况:T(n) =O(nlog2n)

五、简单选择排序

算法简介

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

动图演示

在这里插入图片描述

代码实现

package leetcode;
/**
 * 选择排序
 * @author acer
 *
 */
public class Selection_sort {
	
	public static void main(String[] args) {
		int[]  array= {3,3,345,2,753,4765,734658,567,7};
		int[] arrayNew=Selection_sort.selection_sort(array);
		for (int i = 0; i < arrayNew.length; i++) {
			System.out.print(arrayNew[i]+"     ");
		}
	}
	public static int[] selection_sort(int[] array) {
		if(array.length==0) {
			return array;
		}
		for(int i=0;i<array.length;i++) {
			int minIndex=i;
			for(int j=i;j<array.length;j++) {
				if(array[j]<array[minIndex])//找到最小的数
					minIndex=j;//将最小数的索引保存
			}
			int temp=array[minIndex];
			array[minIndex]=array[i];
			array[i]=temp;
		}
		return array;
	}
}

  • 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

应用场景

当数据量较小的时候适用

算法分析

最佳情况:T(n) = O(n2) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

六、堆排序

算法简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
在这里插入图片描述
在这里插入图片描述

图片演示

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。
  a.假设给定无序序列结构如下
  在这里插入图片描述
  2.此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。

此处必须注意,我们把6和9比较交换之后,必须考量9这个节点对于其子节点会不会产生任何影响?因为其是叶子节点,所以不加考虑;但是,一定要熟练这种思维,写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。
在这里插入图片描述
4.找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

在真正代码的实现中,这时候4和9交换过后,必须考虑9所在的这个节点位置,因为其上的值变了,必须判断对其的两个子节点是否造成了影响,这么说不合适,实际上就是判断其作为根节点的那棵子树,是否还满足大根堆的原则,每一次交换,都必须要循环把子树部分判别清楚。
在这里插入图片描述
这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。

牢记上面说的规则,每次交换都要把改变了的那个节点所在的树重新判定一下,这里就用上了,4和9交换了,变动了的那棵子树就必须重新调整,一直调整到符合大根堆的规则为截。
在这里插入图片描述
此时,我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

这里,必须说明一下,所谓的交换,实际上就是把最大值从树里面拿掉了,剩下参与到排序的树,其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。
在这里插入图片描述
b.重新调整结构,使其继续满足堆定义
在这里插入图片描述
c.再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.
在这里插入图片描述
后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序在这里插入图片描述

代码实现

package leetcode;

import java.util.Arrays;

/**
 * 堆排序
 * @author acer
 *
 */
public class HeapSort {
	public static void main(String[] args) {
		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
		// 接下来就是排序的主体逻辑
		sort(array);
		System.out.println(Arrays.toString(array));
	}
	public static void sort(int[] array) {
		// 按照完全二叉树的特点,从最后一个非叶子节点开始,对于整棵树进行大根堆的调整
		// 也就是说,是按照自下而上,每一层都是自右向左来进行调整的
		// 注意,这里元素的索引是从0开始的
		// 另一件需要注意的事情,这里的建堆,是用堆调整的方式来做的
		// 堆调整的逻辑在建堆和后续排序过程中复用的
		for (int i = array.length / 2 - 1; i >= 0; i--) {
			adjustHeap(array, i, array.length);
		}
 
		// 上述逻辑,建堆结束
		// 下面,开始排序逻辑
		for (int j = array.length - 1; j > 0; j--) {
			// 元素交换
			// 说是交换,其实质就是把大顶堆的根元素,放到数组的最后;换句话说,就是每一次的堆调整之后,都会有一个元素到达自己的最终位置
			swap(array, 0, j);
			// 元素交换之后,毫无疑问,最后一个元素无需再考虑排序问题了。
			// 接下来我们需要排序的,就是已经去掉了部分元素的堆了,这也是为什么此方法放在循环里的原因
			// 而这里,实质上是自上而下,自左向右进行调整的
			adjustHeap(array, 0, j);
		}
	}
 
	/**
	 * 
	 * @description 这里,是整个堆排序最关键的地方,正是因为把这个方法抽取出来,才更好理解了堆排序的精髓,会尽可能仔细讲解
	 * @author
	 * @param
	 * @return
	 * @time 2018年3月9日 下午2:54:38
	 */
	public static void adjustHeap(int[] array, int i, int length) {
		// 先把当前元素取出来,因为当前元素可能要一直移动
		int temp = array[i];
		// 可以参照sort中的调用逻辑,在堆建成,且完成第一次交换之后,实质上i=0;也就是说,是从根所在的最小子树开始调整的
		// 接下来的讲解,都是按照i的初始值为0来讲述的
		// 这一段很好理解,如果i=0;则k=1;k+1=2
		// 实质上,就是根节点和其左右子节点记性比较,让k指向这个不超过三个节点的子树中最大的值
		// 这里,必须要说下为什么k值是跳跃性的。
		// 首先,举个例子,如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整,那么,下一步该到哪个节点了呢?肯定是a[1]所在的子树了,
		// 也就是说,是以本节点的左子节点为根的那棵小的子树
		// 而如果a[0}<a[2]呢,那就调整a[0]和a[2]的位置,然后继续调整以a[2]为根节点的那棵子树,而且肯定是从左子树开始调整的
		// 所以,这里面的用意就在于,自上而下,自左向右一点点调整整棵树的部分,直到每一颗小子树都满足大根堆的规律为止
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			// 让k先指向子节点中最大的节点
			if (k + 1 < length && array[k] < array[k + 1]) {
				k++;
			}
 
			// 如果发现子节点更大,则进行值的交换
			if (array[k] > temp) {
				swap(array, i, k);
				// 下面就是非常关键的一步了
				// 如果子节点更换了,那么,以子节点为根的子树会不会受到影响呢?
				// 所以,循环对子节点所在的树继续进行判断
				i = k;
				// 如果不用交换,那么,就直接终止循环了
			} else {
				break;
			}
		}
	}
 
	/**
	 * 交换元素
	 * 
	 * @param arr
	 * @param a
	 *            元素的下标
	 * @param b
	 *            元素的下标
	 */
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95

应用场景

堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

算法分析

最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

七、二路归并排序

算法简介

分:
1.一直分两组,分别对两个数组进行排序(根据上层对下层在一组的数据通过临时数组排序,再将有序数组挪回上层数组中)。
2. 循环第一步,直到划分出来的“小组”只包含一个元素,只有一个元素的数组默认为已经排好序。
合:(合并时,站在上层合并下层(使组内有序))
1.将两个有序的数组合并到一个大的数组中。
2.从最小的只包含一个元素的数组开始两两合并。此时,合并好的数组也是有序的。最后把小组合成一个组。

图片演示

在这里插入图片描述

代码实现

public class MergeSort {
	
	/**
	 * 归并排序
	 * @param arr
	 * @param left
	 * @param right
	 */
	public static void mergeSort(int[] arr, int left, int right) {
		if(null == arr) {
			return;
		}
		
		if(left < right) {
			//找中间位置进行划分
			int mid = (left+right)/2;
			//对左子序列进行递归归并排序
			mergeSort(arr, left, mid);
			//对右子序列进行递归归并排序
			mergeSort(arr, mid+1, right);
			//“合”。 进行归并
			merge(arr, left, mid, right);
		}
	}
	
	/**
	 * 进行归并
	 * @param arr
	 * @param left
	 * @param mid
	 * @param right
	 */
	private static void merge(int[] arr, int left, int mid, int right) {
		int[] tempArr = new int[arr.length];
		int leftStart = left;
		int rightStart = mid+1;
		int tempIndex = left;
		
		while(leftStart <= mid && rightStart <= right) {
			if(arr[leftStart] < arr[rightStart]) {
				tempArr[tempIndex++] = arr[leftStart++];
			} else {
				tempArr[tempIndex++] = arr[rightStart++];
			}	
		}
		
		while(leftStart <= mid) {
			tempArr[tempIndex++] = arr[leftStart++];
		}
		
		while(rightStart <= right) {
			tempArr[tempIndex++] = arr[rightStart++];
		}
		
		while(left <= right) {
			arr[left] = tempArr[left++];
		}
	}
	
	private static void showArr(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {4, 2, 6, 1, 3, 8, 5, 9};
		/*
		 * 归并排序
		 * 对上下限值分别为0和arr.length-1的记录序列arr进行归并排序
		 */
		mergeSort(arr, 0, arr.length-1);
		showArr(arr);
	}
}

  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76

应用场景

内存空间不足的时候使用归并排序,能够使用并行计算的时候使用归并排序。

算法分析

最佳情况:T(n) = O(n) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

八、计数排序

算法简介

找出待排序的数组中最大和最小的元素;
统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

动图演示

在这里插入图片描述

代码实现

public class CountSort {
	
	private static int[]  countsort(int[] arr) {
		int max=arr[0];
		int min=arr[0];
		
		//step1:得到最大值和最小值,确定构建的数组长度
		for (int i = 0; i < arr.length; i++) {
			
			if(arr[i]>max) {
				max=arr[i];
			}
			if(arr[i]<min) {
				min=arr[i];
			}
		}
		
		//step2:构建一个数组,用来存放每一个数对应出现的次数
		int d=max-min;
		int [] countArray=new int [d+1];
		//统计次数
		for (int i = 0; i < arr.length; i++) {
			countArray[arr[i]-min]++;
		}
		System.out.println("统计不同元素出现的次数:"+Arrays.toString( countArray));
		
		//step3:对此时的数组做变形,统计数组从第二个元素开始,每一个元素等于它本身都加上前面所有元素之和。
		for(int i=1;i<countArray.length;i++) {
			countArray[i]+=countArray[i-1];
		}
		System.out.println("变形后的数组:"+Arrays.toString( countArray));
		
		//step4:倒序遍历原始数列,从统计数组找到正确位置,输出到结果数组,确保稳定性
		int[] sortedArray = new int[arr.length];
		for(int i=arr.length-1;i>=0;i--) {
			
			sortedArray[countArray[arr[i]-min]-1]=arr[i];
			countArray[arr[i]-min]--;
			
		}
		return sortedArray;
	}
	
	public static void main(String[] args) {
		int arr[]={93,95,98,98,94,92,96,91};
		int[] sortedArray=countsort(arr);
		System.out.println("结果输出:"+Arrays.toString(sortedArray));
	}
 
}


  • 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

应用场景

计数排序需要占用大量空间,它仅适用于数据比较集中的情况。比如 [0100],[1000019999] 这样的数据。

算法分析

最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n+k)

九、桶排序

算法简介

桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里。

假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX)。在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0;将容量为MAX的桶数组中的每一个单元都看作一个"桶"。
在排序时,逐个遍历数组a,将数组a的值,作为"桶数组r"的下标。当a中数据被读取时,就将桶的值加1。例如,读取到数组a[3]=5,则将r[5]的值+1。

图片演示

bucketSort(a, n, max)是作用是对数组a进行桶排序,n是数组a的长度,max是数组中最大元素所属的范围[0,max)。
假设a={8,2,3,4,3,6,6,3,9}, max=10。此时,将数组a的所有数据都放到需要为0-9的桶中。如下图:
在这里插入图片描述

代码实现

package leetcode;

/**
 * 桶排序
 * @author acer
 *
 */
public class BucketSort {
 
    /*
     * 桶排序
     *
     * 参数说明:
     *     a -- 待排序数组
     *     max -- 数组a中最大值的范围
     */
    public static void bucketSort(int[] a, int max) {
        int[] buckets;
 
        if (a==null || max<1)
            return ;
 
        // 创建一个容量为max的数组buckets,并且将buckets中的所有数据都初始化为0。
        buckets = new int[max];
 
        // 1. 计数
        for(int i = 0; i < a.length; i++) 
            buckets[a[i]]++; 
 
        // 2. 排序
        for (int i = 0, j = 0; i < max; i++) {
            while( (buckets[i]--) >0 ) {
                a[j++] = i;
            }
        }
 
        buckets = null;
    }
 
    public static void main(String[] args) {
        int i;
        int a[] = {8,2,3,4,3,6,6,3,9};
 
        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
 
        bucketSort(a, 10); // 桶排序
 
        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}


  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n2)

十、基数排序

算法简介

相比其它排序,主要是利用比较和交换,而基数排序则是利用分配和收集两种基本操作。基数 排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。

实现:将所有待比较数值(自然数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的两种方式:
高位优先,又称为最有效键(MSD),它的比较方向是由右至左;
低位优先,又称为最无效键(LSD),它的比较方向是由左至右;

动图演示

在这里插入图片描述
在这里插入图片描述

代码实现

package leetcode;

import java.util.Arrays;

/**
 * 基数排序演示
 *
 * 
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
                194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};

        radixSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * 高位优先法
     *
     * @param arr 待排序列,必须为自然数
     */
    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数

        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }

        //从个位开始,对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];

            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }

            //更改buckets[i],
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }

            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }

            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }

    }
}

  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

算法分析

最佳情况:T(n) = O(n * k) 最差情况:T(n) = O(n * k) 平均情况:T(n) = O(n * k)
基数排序有两种方法:
MSD 从高位开始进行排序 LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
基数排序:根据键值的每位数字来分配桶
计数排序:每个桶只存储单一键值
桶排序:每个桶存储一定范围的数值

一些基本情况

数据有什么特征
有没有可能包含有大量重复的元素
如果有这种可能的话,三路快排是更好地选择
是否数据的取值范围非常有限,比如对学生的成绩排序。
如果是这样的话,计数排序是更好的选择
对排序有什么额外的要求
是否需要稳定排序
如果是的话,归并排序是更好的选择,快排就不怎么好了
数据的存储状况是怎么样的
快排是依赖于数组的随机存储
如果是使用链表存储的
如果是的话,归并排序是更好的选择,
数据的存储状况是怎么样的
数据的大小是否可以装在在内存里
数据量很大或者内存很小,不足以装载在内存里,需要使用外排序算法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/163980
推荐阅读
相关标签
  

闽ICP备14008679号