快速排序(Quicksort)是对冒泡排序的一种改进;
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列;
package com.zb.ds.sort;
import java.util.Arrays;
//快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-9,-8,-7,0,-3,2,-5,9};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr,int left,int right){
int l = left;//左下标
int r = right;//右下标
//pivot:中轴
int pivot = arr[(l + r)/2];
int temp;//临时变量,交换时使用
//while循环的目的是让比pivot小的放到左边,大的放到右边
while (l<r){
//一个循环从左往右,另一个循环从右往左,都好像是在“清除异己”,小于pivot就是左阵营,大于pivot就是右阵营,等于的话都可以
//左阵营每挑出来一个右阵营的就拿去和有阵营挑出来的交换,甚至其中一个阵营没有“异己”了,就拿pivot去交换
//这个时候,右阵营发现左阵营拿pivot跟自己交换,很不开心,要求左阵营往后走一步,这件事情对于左阵营也是这样操作的
//依此循环,目标是pivot左边全部是小于等于pivot的,右边全部是大于等于pivot的
//我们再思考一下满足的条件:左阵营找找找,没找到“异己”,右阵营也找找找,一直找不到“异己”,
//知道左右阵容头碰头了(l=r),或者都找到对方阵营了(l>r),这个时候才做罢休!
//这个时候就可以了退出了,完成任务了,但是退出的条件是l>=r,很显然此时l不一定>=r,因为pivot这个值可能不是唯一的,意思是
//在pivot左边一直找,找到一个大于等于pivot的值才退出
//从左往右,找一个比pivot大的值
while (arr[l]<pivot){
l++;
}
//这个时候l最大的可能是比r小
//这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot前面的数全部比pivot小,
//只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
//在pivot右边一直找,找到一个小于等于pivot的值才退出
//从右往左,找一个比pivot小的值
while (arr[r]>pivot){
r--;
}
//这个时候r最大的可能是比l大
//这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot后面的数全部比pivot大,
//只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
//如果l>=r,说明pivot的左边的值是小于等于pivot的值,右边全部是大于等于pivot的值
//这个地方不好理解,首先要明白pivot是一个值,无关下标,pivot也只是一个普通的arr[l]或者arr[r],会随着规则移动位置
//
if(l>=r){
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换之后发现arr[l]=pivot,r--,前移
if(arr[l]==pivot){
r--;
}
//如果交换之后发现arr[r]=pivot,l++,后移
if(arr[r]==pivot){
l++;
}
}
//在这之前,我们进行了一次阵营查找,下面再将左右阵营分别再划分左右阵营进行“排除异己”操作
//如果l=r,那么这个下标的值就不进行操作了,因为它会始终位于两大阵营中间,也选出了一个数,所有的顺序产生机制就是通过这个方法得出“中间值”
//如果l=r,必须l++,r--,否则会出现栈溢出
if(l==r){
l++;
r--;
}
//递归实现阵营的划分
//向左递归
if(left<r){
sort(arr,left,r);
}
//向右递归
if(right>l){
sort(arr,l,right);
}
}
}
[-9, -8, -7, -5, -3, 0, 2, 9]
package com.zb.ds.sort;
import java.util.Random;
//快速排序
public class QuickSort {
public static void main(String[] args) {
int[] nums = new int[80000];
for (int i = 0; i < 80000; i++) {
nums[i] = new Random().nextInt(8000000);
}
//排序前时间
long start = System.currentTimeMillis();
System.out.println("排序前时间:" + start);
sort(nums,0,79999);
//排序后时间
long end = System.currentTimeMillis();
System.out.println("排序后时间:" + end);
//程序执行时间
System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
}
public static void sort(int[] arr,int left,int right){
int l = left;//左下标
int r = right;//右下标
//pivot:中轴
int pivot = arr[(l + r)/2];
int temp;//临时变量,交换时使用
//while循环的目的是让比pivot小的放到左边,大的放到右边
while (l<r){
//一个循环从左往右,另一个循环从右往左,都好像是在“清除异己”,小于pivot就是左阵营,大于pivot就是右阵营,等于的话都可以
//左阵营每挑出来一个右阵营的就拿去和有阵营挑出来的交换,甚至其中一个阵营没有“异己”了,就拿pivot去交换
//这个时候,右阵营发现左阵营拿pivot跟自己交换,很不开心,要求左阵营往后走一步,这件事情对于左阵营也是这样操作的
//依此循环,目标是pivot左边全部是小于等于pivot的,右边全部是大于等于pivot的
//我们再思考一下满足的条件:左阵营找找找,没找到“异己”,右阵营也找找找,一直找不到“异己”,
//知道左右阵容头碰头了(l=r),或者都找到对方阵营了(l>r),这个时候才做罢休!
//这个时候就可以了退出了,完成任务了,但是退出的条件是l>=r,很显然此时l不一定>=r,因为pivot这个值可能不是唯一的,意思是
//在pivot左边一直找,找到一个大于等于pivot的值才退出
//从左往右,找一个比pivot大的值
while (arr[l]<pivot){
l++;
}
//这个时候l最大的可能是比r小
//这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot前面的数全部比pivot小,
//只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
//在pivot右边一直找,找到一个小于等于pivot的值才退出
//从右往左,找一个比pivot小的值
while (arr[r]>pivot){
r--;
}
//这个时候r最大的可能是比l大
//这个时候找到的下标可能是pivot所在的下标,因为这个时候pivot后面的数全部比pivot大,
//只有找到了他自己才符合跳出循环的条件,所以下标l对应的值应该就是pivot
//如果l>=r,说明pivot的左边的值是小于等于pivot的值,右边全部是大于等于pivot的值
//这个地方不好理解,首先要明白pivot是一个值,无关下标,pivot也只是一个普通的arr[l]或者arr[r],会随着规则移动位置
//
if(l>=r){
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换之后发现arr[l]=pivot,r--,前移
if(arr[l]==pivot){
r--;
}
//如果交换之后发现arr[r]=pivot,l++,后移
if(arr[r]==pivot){
l++;
}
}
//在这之前,我们进行了一次阵营查找,下面再将左右阵营分别再划分左右阵营进行“排除异己”操作
//如果l=r,那么这个下标的值就不进行操作了,因为它会始终位于两大阵营中间,也选出了一个数,所有的顺序产生机制就是通过这个方法得出“中间值”
//如果l=r,必须l++,r--,否则会出现栈溢出
if(l==r){
l++;
r--;
}
//递归实现阵营的划分
//向左递归
if(left<r){
sort(arr,left,r);
}
//向右递归
if(right>l){
sort(arr,l,right);
}
}
}
排序前时间:1606362043150
排序后时间:1606362043169
程序执行时间为:0秒!
80万数据,162毫秒;
800万数据,1秒425毫秒;
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之);
说明: 可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程;
再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤:
package com.zb.ds.sort;
import java.util.Arrays;
public class MergerSort {
public static void main(String[] args) {
int[] arr = {8,4,5,7,1,3,6,2};
int[] temp = new int[arr.length];
mergerSort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
public static void mergerSort(int[] arr,int left,int right,int[] temp){
if(left<right){
int mid = (left + right)/2;//中建索引
//向左递归进行分解
mergerSort(arr,left,mid,temp);
//向右递归进行分解
mergerSort(arr,mid+1,right,temp);
//合并
sort(arr,left,mid,right,temp);
}
}
/**
* 归并排序-合并
* @param arr 待排序数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void sort(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//初始化i,左边有序序列的初始索引
int j = mid + 1;//初始化j,右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//第一步:
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边有一边处理完毕为止
while (i<=mid && j<=right){
//如果发现左边序列的”当前元素“小于等于右边数列的当前元素,就把该元素放到中转数组的“当前位置”
//然后左边序列的”当前位置“和中转数组的”当前位置“后移一位
if(arr[i]<=arr[j]){
temp[t] = arr[i];
t++;
i++;
}else {//反之将右边序列的“当前元素”放到中转数组的“当前位置”
temp[t] = arr[j];
t++;
j++;
}
}
//第二步:
//将有剩余数据的一方,依次填充到temp数组
while (i<=mid){
temp[t] = arr[i];
t++;
i++;
}
while (j<=right){
temp[t] = arr[j];
t++;
j++;
}
//第三步:
//将temp数组的元素拷贝到arr
//注意:并不是每次都拷贝所有
t = 0;
int tempLeft = left;
//第一次合并时,tempLeft=0,right=1;//第二次:tL=2,r=3//第三次:tl=0.r=3//...
//最后一次:tempLeft=0,right=7;
while (tempLeft<=right){
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
[1, 2, 3, 4, 5, 6, 7, 8]
package com.zb.ds.sort;
import java.util.Random;
public class MergerSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = new Random().nextInt(8000000);
}
int[] temp = new int[arr.length];
//排序前时间
long start = System.currentTimeMillis();
System.out.println("排序前时间:" + start);
mergerSort(arr,0,arr.length-1,temp);
//排序后时间
long end = System.currentTimeMillis();
System.out.println("排序后时间:" + end);
//程序执行时间
System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
}
public static void mergerSort(int[] arr,int left,int right,int[] temp){
if(left<right){
int mid = (left + right)/2;//中建索引
//向左递归进行分解
mergerSort(arr,left,mid,temp);
//向右递归进行分解
mergerSort(arr,mid+1,right,temp);
//合并
sort(arr,left,mid,right,temp);
}
}
/**
* 归并排序-合并
* @param arr 待排序数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void sort(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//初始化i,左边有序序列的初始索引
int j = mid + 1;//初始化j,右边有序序列的初始索引
int t = 0;//指向temp数组的当前索引
//第一步:
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边有一边处理完毕为止
while (i<=mid && j<=right){
//如果发现左边序列的”当前元素“小于等于右边数列的当前元素,就把该元素放到中转数组的“当前位置”
//然后左边序列的”当前位置“和中转数组的”当前位置“后移一位
if(arr[i]<=arr[j]){
temp[t] = arr[i];
t++;
i++;
}else {//反之将右边序列的“当前元素”放到中转数组的“当前位置”
temp[t] = arr[j];
t++;
j++;
}
}
//第二步:
//将有剩余数据的一方,依次填充到temp数组
while (i<=mid){
temp[t] = arr[i];
t++;
i++;
}
while (j<=right){
temp[t] = arr[j];
t++;
j++;
}
//第三步:
//将temp数组的元素拷贝到arr
//注意:并不是每次都拷贝所有
t = 0;
int tempLeft = left;
//第一次合并时,tempLeft=0,right=1;//第二次:tL=2,r=3//第三次:tl=0.r=3//...
//最后一次:tempLeft=0,right=7;
while (tempLeft<=right){
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
排序前时间:1606446334005
排序后时间:1606446334020
程序执行时间为:0秒!
①基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用;
②基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法;
③基数排序(Radix Sort)是桶排序的扩展;
④基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较;
将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列;
将数组 {53,3,542,748,14,214} 使用基数排序,进行升序排序:
说明:事先准备10个数组(10个桶), 0-9 分别对应 位数的 0-9;
(1) 将各个数,按照个位大小放入到对应的各个数组中;
(2) 然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;
第1轮排序后:542 53 3 14 214 748
(1) 将各个数,按照十位大小放入到对应的各个数组中;
(2) 然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;
第2轮排序后: 3 14 214 542 748 53
(1) 将各个数,按照百位大小放入到对应的各个数组中;
(2) 然后从0-9个数组/桶,依次按照加入元素的先后顺序取出;
第3轮排序后:3 14 53 214 542 748
package com.zb.ds.sort;
import java.util.Arrays;
//基数排序(桶排序)
public class RadixSort {
public static void main(String[] args) {
int[] arr = {53, 3, 542, 748, 14, 214};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
//拿到数组中最大的数的位数
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
//最大的数的位数
int maxLength = (max + "").length();
//准备一个二维数组,表示10个桶,每一个桶就是一个一维数组
//为了防止数据溢出,每个一维数组的长度为arr.length
//用空间换时间的算法
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组进行记录
int[] bucketElementCounts = new int[10];
//开始排序
for (int x=0,n=1; x<maxLength; x++,n*=10) {
//1、第1轮排序[按照个位排序]
for (int value : arr) {
//取出每个元素个位数的值
int digitOfElement = value / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
bucketElementCounts[digitOfElement]++;//后移一位
}
//此时此刻,第一轮排序完毕,我们需要从0-9个数组/桶,依次按照加入元素的先后顺序取出
int index = 0;
//遍历每一个桶,并将所有数据放入原数组
for (int i = 0; i < 10; i++) {
//如果同种有数据,我们才放入原数组
if(bucketElementCounts[i]!=0){
//有数据,遍历该桶
for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];
index++;
}
bucketElementCounts[i]=0;
}
}
}
}
}
[3, 14, 53, 214, 542, 748]
package com.zb.ds.sort;
import java.util.Random;
//基数排序(桶排序)
public class RadixSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = new Random().nextInt(8000000);
}
//排序前时间
long start = System.currentTimeMillis();
System.out.println("排序前时间:" + start);
sort(arr);
//排序后时间
long end = System.currentTimeMillis();
System.out.println("排序后时间:" + end);
//程序执行时间
System.out.println("程序执行时间为:" + (end-start)/1000 + "秒!");
}
public static void sort(int[] arr){
//拿到数组中最大的数的位数
int max = arr[0];
for (int value : arr) {
if (value > max) {
max = value;
}
}
//最大的数的位数
int maxLength = (max + "").length();
//准备一个二维数组,表示10个桶,每一个桶就是一个一维数组
//为了防止数据溢出,每个一维数组的长度为arr.length
//用空间换时间的算法
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组进行记录
int[] bucketElementCounts = new int[10];
//开始排序
for (int x=0,n=1; x<maxLength; x++,n*=10) {
//1、第1轮排序[按照个位排序]
for (int value : arr) {
//取出每个元素个位数的值
int digitOfElement = value / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
bucketElementCounts[digitOfElement]++;//后移一位
}
//此时此刻,第一轮排序完毕,我们需要从0-9个数组/桶,依次按照加入元素的先后顺序取出
int index = 0;
//遍历每一个桶,并将所有数据放入原数组
for (int i = 0; i < 10; i++) {
//如果同种有数据,我们才放入原数组
if(bucketElementCounts[i]!=0){
//有数据,遍历该桶
for (int j = 0; j < bucketElementCounts[i]; j++) {
arr[index] = bucket[i][j];
index++;
}
bucketElementCounts[i]=0;
}
}
}
}
}
排序前时间:1606529012580
排序后时间:1606529012600
程序执行时间为:0秒!
800万数据,632毫秒!
8000万数据,5857毫秒!
但是基数排序比较吃内存!
(学完二叉树,再学堆排序,这里暂时省略,之后补上)
(里面的计数排序和桶排序与基数排序思路大体一致)
①稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
②不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
③内排序:所有排序操作都在内存中完成;
④外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
⑤时间复杂度: 一个算法执行所耗费的时间;
⑥空间复杂度:运行完一个程序所需内存的大小。 n: 数据规模 k: “桶”的个数 In-place: 不占用额外内存 Out-place: 占用额外内存;