排序也称排序算法（Sort Algorithm），排序是将一组数据，依照指定的顺讯进行排列的过程。
排序的分类：
1）内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序。内部排序有插入排序（直接插入或希尔排序）、选择排序（简单排序和堆排序）、交换排序（冒泡排序和快速排序）、归并排序、基数排序。
2）外部排序法：数据量太大，无法全部加载到内存中，需要借助外部存储进行排序。
- 冒泡排序 #
- 选择排序 #
- 插入排序 #
- 希尔排序 #
- 快速排序 #
- 归并排序 #
- 基数排序 #
- 常用排序算法总结和对比 #
1、冒泡排序
冒泡排序的原理是将两个相邻的元素相互比较，将较大（或小）的数与后一个元素交换位置。这样通过多轮的比较，每一轮将最大（或最小）的元素排在队列的最后，次最后，次次最后…。就可以将队列排好。
冒泡排序的案例：
冒泡排序法则：
1、 排序次数为数组长度-1（外循环）
2、 每一次排序需要比较的次数逐渐减少，第n次排序的比较次数为数组长度-n-1次（内循环）
例：数组 {1,3,4,2} 数组长度 4
外循环次数为（4-1） 次
内循环次数为（4-当前排序次数-1）次
以下案例不仅有冒泡排序的功能，还可以自定义倒序逆序排序规则，其中还添加了冒泡排序的优化方法。
public class BubbleSort {
public static void bubbleSort(int[] arr,Sort sortType){
for (int i = 1; i < arr.length; i++) {
boolean flag = false; //用于判断是否发生了数字交换
for (int j = 0; j < arr.length-i; j++) {
int a = arr[j];
int b = arr[j+1];
if(sortType==Sort.POSITIVE_SEQUENCE&&a > b){//正序将大的值往后放
arr[j+1] = a;
arr[j] = b;
flag = true;
}else if(sortType==Sort.INVERTED_ORDER&&a < b){//倒序将小的值往后放
arr[j+1] = a;
arr[j] = b;
flag = true;
}
}
if(!flag){
System.out.printf("已排序完成，当前排序是第%d次排序。n",i);
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[8000];
for (int i = 0; i < 8000; i++) {
arr[i] = new Random().nextInt(8000);
}
long begin = System.currentTimeMillis();
bubbleSort(arr,Sort.POSITIVE_SEQUENCE);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000 + "s");
}
}
enum Sort{
POSITIVE_SEQUENCE,
INVERTED_ORDER
}
2、选择排序
选择排序是内部排序法，这种算法是经过先比较查找队列中的最大（小）排在首位，再比较首位后面的最大（小）放在次首位，这样依次查找，直到队列排序完成。选择排序的每次查找只会进行一次交换。
代码实现
public class SelectionSort {
public static void sort(int[] arr,Sort sortType){
for (int i = 0; i < arr.length-1; i++) {
int k = i;//最大（小）值的下标，初始默认为当前元素
for (int j = i +1; j < arr.length; j++) {
if(sortType == Sort.POSITIVE_SEQUENCE && arr[k] > arr[j]){
k = j;//保存更小的小标
}else if(sortType == Sort.INVERTED_ORDER && arr[k] < arr[j]){
k = j;
}
}
//将得到的最大（小）值与当前排序位置交换
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
public static void main(String[] args) {
int[] arr = new int[8000];
for (int i = 0; i < 8000; i++) {
arr[i] = new Random().nextInt(8000);
}
long begin = System.currentTimeMillis();
SelectionSort.sort(arr,Sort.INVERTED_ORDER);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000+"选择排序的效率为秒");
for (int i : arr) {
System.out.print(i+"t");
}
}
}
enum Sort{
POSITIVE_SEQUENCE,
INVERTED_ORDER
}
3、插入排序
插入排序的思想是将要排序的数据队列看成是一个有序列表与无序列表的组合，将第一个值arr[0]看成是一个有序值，使arr[1]的值与arr[0]进行比较，根据比较结果排序为一个新的有序列表，再将arr[2]的值与前面的有序列表的值进行比较。这样每一次后面的值都要和有序列表中的值进行比较排序，这样就完成数据队列的排序。
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
long begin = System.currentTimeMillis();
insertSort(arr);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000 + "s");
}
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
for(int i = 1; i < arr.length; i++) {
insertVal = arr[i];//要比较的值
insertIndex = i - 1;//前一个元素下标
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// 元素后移
insertIndex--;
}
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
}
插入排序存在的问题：当要排序的队列预料排在前面的数据在此队列的最末，这个时候后移（交换）的 *** 作过多。解决方案（使用希尔排序进行优化）
4、希尔排序
希尔排序是对简单插入排序的一个优化。希尔排序的思想是：将要排序的队列按照一定的增量进行分组，对每组使用插入排序算法排序；随着增量的逐渐减少，每组包含的元素越来越多，当增量减至1时，整个队列恰被分成一组，算法终止。
public class ShellSort {
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
shellSort2(arr);
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int[] arr1 = new int[80000];
for (int i = 0; i < 80000; i++) {
arr1[i] = (int) (Math.random() * 8000000);
}
long begin = System.currentTimeMillis();
shellSort(arr1);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000 + "s");//测试时长12s
int[] arr2 = new int[80000];
for (int i = 0; i < 80000; i++) {
arr2[i] = (int) (Math.random() * 8000000);
}
long begin2 = System.currentTimeMillis();
shellSort2(arr2);
long end2 = System.currentTimeMillis();
System.out.println((double)(end2-begin2)/1000 + "s");//测试时长0.023s
}
//交换法
public static void shellSort(int[] arr){
int temp = 0;
for (int gap = arr.length/2; gap > 0;gap /= 2) {
//希尔排序的第一轮排序
//因为第1轮排序，是将10个数据分成了5组
for (int i = gap; i < arr.length; i++) {
//遍历各组中的元素，步长为5
for (int j = i-gap; j >= 0; j -= gap) {
if(arr[j] > arr[j+gap]){
temp = arr[j];
arr[j] = arr[j+gap];
arr[j+gap] = temp;
}
}
}
}
}
//位移法
public static void shellSort2(int[] arr){
for (int gap = arr.length/2; gap > 0;gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-gap]){
while (j - gap >= 0 && temp < arr[j-gap]){
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
}
5、快速排序法
快速排序的思路：通过一次排序将要排序的队列分隔为两个队列，其中的一个队列的中的数据恒小于另一个队列中的值。在通过同样的算法（递归）将两个队列中的数对这两部分数分别进行排序，以此使整个队列成为一个有序列表。
public class QuickSort {
public static void main(String[] args) {
// int[] arr = {-9,78,23,-567,70};
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = new Random().nextInt(800000);
}
long begin = System.currentTimeMillis();
QuickSort.sort(arr,0,arr.length-1);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000);//测试结果为0.03s
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void sort(int[] arr,int left,int right){
int l = left;//左下标
int r = right;//右下标
//pivot 中数
int pivot = arr[(left + right)/2];
int temp = 0;
//while循环的目的是让比pivot 值小的放到左边
//比pivot大的值放在右边
while (l < r){
//从pivot左边向右找，找到小于等于pivot值的才退出
while (arr[l] < pivot){
l += 1;
}
//从pivot右边向左找，找到大于等于pivot值的才退出
while (arr[r] > pivot){
r -= 1;
}
//l和r左右两边都是有序的了就退出
if(l >= r){
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完后，发现这个arr[l] = pivot -- 前移
if(arr[l] == pivot){
r -= 1;
}
// 3 4 5 标数4
//如果交换完后，发现这个arr[r] = pivot ++ 后移
if(arr[r] == pivot){
l += 1;
}
}
if(l == r){
l += 1;
r -= 1;
}
//向左递归
if(left < r){
sort(arr,left,r);
}
//向右递归
if(right > l){
sort(arr,l,right);
}
}
}
6、归并排序法
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
int temp[] = new int[arr.length];
long begin = System.currentTimeMillis();
mergeSort(arr,0,arr.length-1,temp);
long end = System.currentTimeMillis();
System.out.println((double)(end-begin)/1000 + "s");//测试时长0.014s
}
//合并的方法
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//右边有序序列的初始索引
int j = mid + 1;//初始化j,右边有序序列的初始索引
int t = 0;//temp数组的当前索引
//(一)
//先把左右两边（有序）的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕为之
while (i <= mid && j <= right){//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，拷贝到temp数组
//然后 t++ , i++
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t += 1;
i += 1;
} else{//反之，将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//将有剩余数据的一方的数据依次全部填充到temp
while (i <= mid){//左边有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right){
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr
t = 0;
int tempLeft = left;
while (tempLeft <= right){//第一次合并 tempLeft
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
//分 + 合的方法
public static void mergeSort(int[] arr,int left,int right,int[] temp){
if(left < right){
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr,left,mid,temp);
//向右递归进行分解
mergeSort(arr,mid +1,right,temp);
//合并
merge(arr,left,mid,right,temp);
}
}
}
7、基数排序
基数排序是桶排序的实现。它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，将整数按位数切割成不同的数字，然后按每个位数分别比较，达到排序的作用。基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法。
基数排序的基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
public class RadixSort {
public static void main(String[] args) {
// int arr[] = { 53, 3, 542, 748, 14, 214};
// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 80000);
}
long begin = System.currentTimeMillis();
radixSort(arr);
long end = System.currentTimeMillis();
System.out.println((double) (end - begin) / 1000 + "s");
// for (int i : arr) {
// System.out.print(i + " ");
// }
}
public static void radixSort(int[] arr) {
int max = arr[0];
for(int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxLength = (max + "").length();
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10];
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
for(int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / n % 10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
int index = 0;
for(int k = 0; k < bucketElementCounts.length; k++) {
if(bucketElementCounts[k] != 0) {
for(int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;
}
}
}
}
8、常用排序算法的总结与对比
相关术语解释：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序：所有排序 *** 作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度： 一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
n: 数据规模
k: “桶”的个数
In-place: 不占用额外内存
Out-place: 占用额外内存
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）