文章目录
- 排序的概念及引用
- 1.插入排序
- 2.希尔排序(缩小增量排序)
- 3.选择排序
- 4.堆排序
- 5.冒泡排序
- 6.快速排序
- 7.归并排序
- 8.代码排序部分的测试
- 9.代码加效果大致测试时间（仅供参考）
排序的概念及引用
排序:将数据按照特定的规律排成递增或递减的操作
稳定性:例如arr数组中arr[i]==arr[i+1]但在排序后arr[i+1]排在arr[i]前面了则是不稳定的反之稳定
已下方法都是按照递增排序的。
swap方法（交换）代码：
private static void swap(int []arr,int ret1,int ret2){
int temp=arr[ret1];
arr[ret1]=arr[ret2];
arr[ret2]=temp;
}
1.插入排序
基本思路将指定的数插入到了原本已经有序的数组中，直到数组全部有序。
在此写了两种方法，变化不大。
public static void paixu1(int arr[]){
for(int i=1;i<arr.length;i++){
int temp=arr[i];
for ( int j=i-1;j>=0;j--){
if(arr[j]>temp){//直接插入到arr[j]位置
arr[j+1]=arr[j];
arr[j]=temp;
}
else {
break;
}
}
}
}
public static void paixu2(int arr[]){
for(int i=1;i<arr.length;i++){
int temp=arr[i];
int j=i-1;
for (;j>=0;j--){
if(arr[j]>temp){
arr[j+1]=arr[j];//找到temp的正确位置
}
else {
break;
}
}
arr[j+1]=temp;//找到后再插入
}
}
插入排序:时间复杂度为O(n~n^2);空间复杂度为O(1)；稳定
2.希尔排序(缩小增量排序)
基本思路:将数组分为gap小组进行排序，直到gap为1该数组就完成了排序，使用的底层排序逻辑就是在插入排序的基础下优化。
public static void haset(int arr[]) {
int gap = arr.length;
while (gap >1) {
gap /= 2;
hpa(arr,gap);
}
}
private static void hpa(int arr[],int gap){
for(int i=1;i<arr.length;i++){
int temp=arr[i];
int j=i-gap;
for (;j>=0;j-=gap){
if(arr[j]>temp){
arr[j+gap]=arr[j];
}
else {
break;
}
}
arr[j+gap]=temp;
}
}
希尔排序:时间复杂度为O(n~n^2);空间复杂度为O(1);不稳定
3.选择排序
基本思路：在需要排序的数据中找出最大或最小的值放在特定位置后面按照这样继续遍历数组直至数组遍历完成。
public static void xtion1(int arr[]){
for (int i=0;i< arr.length;i++){
int temp=i;
for (int j=i+1;j< arr.length;j++){
if(arr[j]<arr[temp]) {
temp= j;
}
}
if(arr[temp]<arr[i]){
swap(arr,i,temp);
}
}
}
在此基础上可以进行优化一次性找出最大和最小
public static void xtion2(int arr[]){
int left=0;
int right=arr.length-1;
while(left<right){
int minindex= left;
int maxindex=left;//用maxindex=right就需要去套两个for循环增加运行时间
for(int i=left+1;i<=right;i++){
if(arr[i]<arr[minindex]){
minindex=i;
}
if(arr[i]>arr[maxindex]){
maxindex=i;
}
}
swap(arr,left,minindex);
//注意第一个数是最大值就需要特殊处理防止刚换过的最小又去换去最大值的位置这个逻辑就直接崩了
if(left==maxindex){
maxindex=minindex;
}
swap(arr,right,maxindex);
left++;
right--;
}
}
选择排序:时间复杂度为O(n^2);空间复杂度为O(1);不稳定
4.堆排序
基本思路：运用堆的性质排序。
我们需要的是递增排序所以使用大堆然后交换0下标与end下标进行end–再进行向下调整。
代码：
public static void duipa(int []arr){
int end= arr.length-1;
dadui(arr,end);//构建堆的过程可以使用xiato方法代替可以节省大量时间消耗（才符合时间复杂度O(n*logn)），这里就直接展示如何构建堆的过程了
while (end>0){
swap(arr,0,end);
//只需要向下调整
end--;
xiato(arr,end);
}
}
private static void xiato(int[]arr,int end) {
int parten=0;
int childer = parten * 2 + 1;
while (childer <= end) {
if (childer + 1 <= end&& arr[childer] < arr[childer + 1]) {
childer++;
}
if (arr[parten] < arr[childer]) {
swap(arr, parten, childer);
parten = childer;
childer = parten * 2 + 1;
} else {
break;
}
}
}
private static void swap(int[]arr,int ret1,int ret2){
int temp=arr[ret2];
arr[ret2]=arr[ret1];
arr[ret1]=temp;
}
private static void dadui(int []arr,int end){
int usize= end;
for (int parten=(usize-1)/2;parten>=0;parten--){
int childer=parten*2+1;
while(childer<=usize){
if(childer+1<=usize&&arr[childer]<arr[childer+1]){
childer++;
}
if(arr[parten]<arr[childer]){
swap(arr,parten,childer);
parten=childer;
childer=parten*2+1;
}
else{
break;
}
}
}
}
堆排序:时间复杂度为O(n*logn)；空间复杂度为O(1);不稳定
5.冒泡排序
基本思路:基于指定数据与其余数据相比进行交换。
代码:
public static void mppx(int []arr){
for (int i = 0; i <arr.length ; i++) {
for (int j = 0; j< arr.length-1-i; j++) {//一次次确定最大值
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
在此基础上进行优化，优化的思路为当数组已经排好了就可以直接退出循环减少时间的消耗。
优化代码:
```java
public static void mppx(int []arr){
for (int i = 0; i <arr.length ; i++) {
boolean flag=false;//作为标记是否有进行交换
for (int j = 0; j< arr.length-1-i; j++) {//一次次确定最小值
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
flag=true;
}
}
if(!flag){//说明没有进入第二层循环却没有进行交换代表已经排好了
break;
}
}
}
冒泡排序:时间复杂度为O(n^2)；空间复杂度为O(1)；稳定
6.快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌。
三种不同方法：Hoare版，挖坑法，前后指针法。
cent方法是便于找到了数组的中位数去大大优化代码的时间消耗，当第一次就找到中间值去分割是优解所以创建cent方法去找去中位数。
private static int cent(int []arr,int start,int end){//找中位数的下标
int mid=(start+end)/2;
if(arr[start]<arr[end]){
if(arr[mid]<arr[start]){
return start;
}
if(arr[mid]>arr[end]){
return end;
}
else{
return mid;
}
}
else {
if(arr[mid]>arr[start]){
return start;
}
if(arr[mid]<arr[end]){
return end;
}
else{
return mid;
}
}
}
Hoare:分为递归与非递归
代码1递归：
去注意为什么利用递归和什么时候需要递归的跑代码和递归结束的条件能更好的理解。
public static void quikpai(int[]arr){
quik(arr,0, arr.length-1);
}
private static void quik(int[]arr,int start,int end){
if(start>=end){//注意递归结束的条件
return;
}
swap(arr,start,cent(arr,start,end));
int cent=quike(arr,start,end);
quik(arr,start,cent-1);
quik(arr,cent+1,end);
}
//作用于找到了指定值的下标而且将其中分为小于和大于指定值的左右两边
private static int quike(int []arr,int start,int end){
int cent=start;
while(start<end){
while (start<end&&arr[end]>=arr[cent]){
end--;
}
while (start<end&&arr[start]<=arr[cent]){
start++;
}
swap(arr,start,end);
}
swap(arr,cent,start);
return start;
}
代码2非递归:
变动的是quik方法
public static void quikpai1(int[]arr){
quik1(arr,0, arr.length-1);
}
private static void quik1(int[]arr,int start,int end){//不使用递归去快排
swap(arr,start,cent(arr,start,end));
int cent=quike(arr,start,end);
Stack<Integer> stack=new Stack<>();
if(cent>start+1){
stack.push(start);
stack.push(cent-1);
}
if(cent<end-1){
stack.push(cent+1);
stack.push(end);
}
end=stack.pop();
start=stack.pop();
cent=quike(arr,start,end);
while (!stack.isEmpty()){
if(cent>start+1){
stack.push(start);
stack.push(cent-1);
}
if(cent<end-1){
stack.push(cent+1);
stack.push(end);
}
end=stack.pop();
start=stack.pop();
cent=quike(arr,start,end);
}
}
private static int quike(int []arr,int start,int end){
int cent=start;
while(start<end){
while (start<end&&arr[end]>=arr[cent]){
end--;
}
while (start<end&&arr[start]<=arr[cent]){
start++;
}
swap(arr,start,end);
}
swap(arr,cent,start);
return start;
}
挖坑法:
基本思路与Hoare相似，将指定数据下标挖坑；先从end开始向后找到小于指定值的数填入坑中这个坑就是被找到这个值代替了再从start开始向前找到大于指定值的数填入后面的这个新坑中，最后start>=end时再将指定值填入这个坑(数组下标)中。
代码：
public static void wquikpai(int []arr){
wquik(arr,0, arr.length-1);
}
private static void wquik(int[]arr,int start,int end){
if(start>=end){
return;
}
int cent=wquike(arr,start,end);
wquik(arr,start,cent-1);
wquik(arr,cent+1,end);
}
private static int wquike(int []arr,int start,int end){
int cent=start;
int paiv=arr[start];
while(start<end){
while (start<end&&arr[end]>=paiv){
end--;
}
arr[start]=arr[end];
while (start<end&&arr[start]<=arr[cent]){
start++;
}
arr[end]=arr[start];
}
arr[start]=paiv;
return start;
}
前后指针法
基本思路:int pavi=start ,int cur=start+1 去根据特定条件去使pavi下标停在第一个出现大于arr[start]的下标上而cur停在pavi停好后出现的第一个小于arr[start]的下标上然后两者进行交换，当cur>arr.length()-1结束。
public static void shuang(int []arr){
wshuang(arr,0,arr.length-1);
}
private static void wshuang(int []arr,int start,int end){
if(start>end){
return;
}
int ret=wshuange(arr,start,end);
wshuang(arr,0,ret-1);
wshuang(arr,ret+1,end);
}
private static int wshuange(int[]arr,int start,int end){
int pavi=start;
int cur=start+1;
while (cur<=end){
if(arr[cur]<arr[start]&&arr[++pavi]!=arr[cur]){//这里是关键
swap(arr,pavi,cur);
}
cur++;
}
//pavi停的位置就是arr[start]的位置；
swap(arr,pavi,start);
return pavi;
}
快速排序的时间复杂度为O(n*logn);空间复杂度为O(logn),不稳定
7.归并排序
基本思路:将数组一直对半分直至数据一个个，在将其两两排序结合，直至整个数组排好。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并
递归方式代码：
public static void merg(int []arr){
mergsort(arr,0,arr.length-1);
}
private static void mergsort(int []arr,int start,int end){
if(start==end){
return;
}
int mid=(start+end)/2;
mergsort(arr,start,mid);
mergsort(arr,mid+1,end);
merghebin(arr,start,end,mid);
}
private static void merghebin(int []arr,int start,int end,int mid){
int se=start;
int sl=mid;
int te=mid+1;
int tl=end;
int []temparr=new int[end-start+1];
int k=0;//表示temparr的下标
while (se<=sl&&te<=tl){
if(arr[se]<=arr[te]){
temparr[k++]=arr[se++];
}
else {
temparr[k++]=arr[te++];
}
}
while (se<=sl){
temparr[k++]=arr[se++];
}
while (te<=tl){
temparr[k++]=arr[te++];
}
for(int i=0;i<end-start+1;i++){
arr[i+start]=temparr[i];
}
}
非递归代码:
public static void merg1(int[]arr){
mergsort1(arr,0,arr.length-1);
}
public static void mergsort1(int[]arr,int start,int end){//采用非递归的方式
int gap=1;
while (gap<arr.length) {
for (int i = 0; i < arr.length; i += 2 * gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if(mid>=arr.length){
mid=arr.length-1;
}
if(right>=arr.length){
right=arr.length-1;
}
merghebin(arr, left,right,mid);
}
gap *= 2;
}
}
private static void merghebin(int []arr,int start,int end,int mid){
int se=start;
int sl=mid;
int te=mid+1;
int tl=end;
int []temparr=new int[end-start+1];
int k=0;//表示temparr的下标
while (se<=sl&&te<=tl){
if(arr[se]<=arr[te]){
temparr[k++]=arr[se++];
}
else {
temparr[k++]=arr[te++];
}
}
while (se<=sl){
temparr[k++]=arr[se++];
}
while (te<=tl){
temparr[k++]=arr[te++];
}
for(int i=0;i<end-start+1;i++){
arr[i+start]=temparr[i];
}
}
归并排序时间复杂度为O(n*logn);空间复杂度为O(n);稳定。
总结七大排序的时间复杂度，空间复杂度，稳定性
8.代码排序部分的测试
public static void main(String[] args) {
int []arr1={5,6,4,2,7,9,1,2};
paixu1(arr1);
System.out.println("插叙1排序"+Arrays.toString(arr1));
int []arr2={64,45,15,51,1,5,31};
paixu2(arr2);
System.out.println("插叙2排序"+Arrays.toString(arr2));
int []arr3={64,112,56,46,95};
haset(arr3);
System.out.println("希尔排序"+Arrays.toString(arr3));
int []arr4={64,45,15,51,1,5,31,88,46,95};
xtion1(arr4);
System.out.println("选择排序1"+Arrays.toString(arr4));
int []arr5={10,6,4,2,7,9,1,2};
xtion2(arr5);
System.out.println("选择排序2"+Arrays.toString(arr5));
int []arr6={8,6,91,3,56,1,656,2};
duipa(arr6);
System.out.println("堆排序"+Arrays.toString(arr6));
int []arr7={2,1,3,7,5};
mppx(arr7);
System.out.println("冒泡排序"+Arrays.toString(arr7));
int []arr8={8,6,4,2,7,9,1,2};
quikpai(arr8);
System.out.println("Hoare快速排序"+Arrays.toString(arr8));
int []arr9={4,5,8,1,2,9,11,15,88};
wquikpai(arr9);
System.out.println("挖坑法快速排序"+Arrays.toString(arr9));
int []arr10={4,5,8,1,2,9,11,88,18};
shuang(arr10);
System.out.println("前后指针法快排"+Arrays.toString(arr10));
int []arr11={4,5,8,1,2,9,11,88,18};
quikpai1(arr11);
System.out.println("非递归快排"+Arrays.toString(arr11));
int []arr12={45,65,45,89,97,111,12,1,2,5,6};
merg(arr12);
System.out.println("递归法归并排序"+Arrays.toString(arr12));
int []arr13={45,65,45,89,97,111,12,1,2,5,6};
merg1(arr13);
System.out.println("非递归归并排序"+Arrays.toString(arr13));
}
9.代码加效果大致测试时间（仅供参考）
数据随机时：
数据逆序时:
import java.util.Arrays;
import java.util.Random;
public class time {
public static void fuztarr(int []arr){
for(int i=0;i<arr.length;i++){//数据逆序
arr[i]=arr.length-i;
}
}
public static void wfuzarr(int []arr){
Random random=new Random(10000);//数据随机
for (int i=0;i<arr.length;i++){
arr[i]=random.nextInt();
}
}
public static void chaxu1(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.paixu1(arr);
long end1=System.currentTimeMillis();
System.out.println("插叙1排序的时间:"+(end1-start1));
}
public static void chaxu(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.paixu2(arr);
long end1=System.currentTimeMillis();
System.out.println("插叙排序的时间:"+(end1-start1));
}
public static void xtion(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.xtion1(arr);
long end1=System.currentTimeMillis();
System.out.println("选择排序的时间:"+(end1-start1));
}
public static void qike(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.quikpai(arr);
long end1=System.currentTimeMillis();
System.out.println("Hoare快速排序的时间:"+(end1-start1));
}
public static void wqike(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.wquikpai(arr);
long end1=System.currentTimeMillis();
System.out.println("挖坑法快速排序的时间:"+(end1-start1));
}
public static void shenqike(int[]arr){
arr= Arrays.copyOf(arr,arr.length);
long start1=System.currentTimeMillis();
test.shuang(arr);
long end1=System.currentTimeMillis();
System.out.println("前后指针快速排序的时间:"+(end1-start1));
}
public static void haxu(int []arr){
arr= Arrays.copyOf(arr,arr.length);
long start2=System.currentTimeMillis();
test.haset(arr);
long end2=System.currentTimeMillis();
System.out.println("希尔排序的时间:"+(end2-start2));
}
public static void mp(int []arr){
arr= Arrays.copyOf(arr,arr.length);
long start2=System.currentTimeMillis();
test.mppx(arr);
long end2=System.currentTimeMillis();
System.out.println("冒泡排序的时间:"+(end2-start2));
}
public static void main(String[] args) {
//测试数据要稍微大，不然都是0.多少毫秒都是显示0不能直观的表示
int []arr=new int [15000];
//fuztarr(arr);
wfuzarr(arr);
chaxu1(arr);
chaxu(arr);
haxu(arr);
mp(arr);
xtion(arr);
qike(arr);
}
}
