目錄
一、插入排序
二、 希爾排序
三、選擇排序
四、冒泡排序
五、堆排序
六、快速排序
挖坑法
6.1、遞回實作
6.2、非遞回實作(遍歷實作)
七、歸并排序
7.1、遞回實作
7.2、非遞回實作(遍歷實作)
一、插入排序
思路：
在我看來插入排序就是先將一段數列變得有序，在將后面的數字不斷的插入到這個有序數列中來的這種方法叫做插入排序，
步驟：
我們可以把第一個數字看成一個有序數列，從第二個開始回圈遍歷，在遍歷的途中在定義一個回圈，不斷的與前面的有序數列進行比較，找到位置之后結束本次回圈，并將數字插入到有序數列中去，從而達成目的，
代碼實作：
public static void insertSort(int[] array) {
for(int i=1;i< array.length;i++){
int j=0;
int temp=array[i];
for(j=i-1;j>=0;j--){
if(temp<array[j]){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=temp;
}
}時間復雜度：最壞的情況下為O(N^2),此時整個數列接近逆序，最好情況下為O(N),此時整個數列接近有序，
空間復雜度：O(1)；
穩定
插入排序越有序，時間效率越高，
二、 希爾排序
思路：
希爾排序就是一種變相的插入排序，通過不斷的變化和調整讓希爾排序的時間效率更加的快捷和方便，
步驟：
1.先選定一個小于length的整數key作為第一增量，然后將所有距離為key的元素分在同一組，并對每一組的元素進行直接插入排序，然后再取一個比第一增量小的整數作為第二增量(我們一般是除2)，重復整個操作，
2.當增量的大小減到1時，就相當于整個序列被分到一組，進行一次直接插入排序，排序完成，
代碼實作：
public static void insertSort(int[] array,int val) {
for(int i=val;i< array.length;i++){
int j=0;
int temp=array[i];
for(j=i-val;j>=0;j-=val){
if(temp<array[j]){
array[j+val]=array[j];
}else {
break;
}
}
array[j+val]=temp;
}
}
public static void shellSort(int[] array) {
int key=array.length;
while (key>0){
key=key/2;
insertSort(array,key);
}
}時間復雜度：最壞的情況下為O(N^2)，最好情況下為O(N),此時整個數列接近有序，平均的情況下為O(N^1.3)左右，
空間復雜度：O(1)；
不穩定
三、選擇排序
思路：
選擇排序就是確定一個陣列的最小值之后將它固定在起始位置，然后繼續回圈確定，直到完成為止，
代碼實作：
public static void selectSort01(int[] array) {
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
}代碼優化：
public static void selectSort01(int[] array) {
for(int i=0;i<array.length;i++){
int tmp=i;//把最小的放入tmp中，進行交換
for(int j=i+1;j<array.length;j++){
if(array[tmp]>array[j]){
tmp=j;
}
}
int temp=array[i];
array[i]=array[tmp];
array[tmp]=temp;
}
}時間復雜度：O(N^2)；
空間復雜度：O(1)；
不穩定
四、冒泡排序
思路：
通過比較j和j+1的值來進行交換，將最大的值鎖定在最后一個，進行回圈，
代碼實作：
public static void bubbleSort01(int[] array) {
for(int i=0;i<array.length;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}代碼優化：
public static void bubbleSort02(int[] array) {
for(int i=0;i<array.length;i++){
boolean b=false;
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
b=true;
}
}
if(b==false){
break;
}
}
}時間復雜度：O(N^2)；
空間復雜度：O(1)；
穩定
五、堆排序
思路：
我們要使用堆排序，那么我們實作要講陣列變成一個大堆，在通過頭和尾進行調換、鎖定，進行排序，詳細的關于堆排序的文章看這個：堆排序，
代碼實作：
public static void shiftDown(int[] array,int parent,int len){
int child=parent*2+1;
while (child<len){
if(child+1<len && array[child+1]>array[child]){
child++;
}
if(array[child]>array[parent]){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
parent=child;
child=child*2+1;
}else {
break;
}
}
}
public static void createBigHeap(int[] array){
for(int i=(array.length-2)/2;i>=0;i--){
shiftDown(array,i,array.length);
}
}
public static void heapSort(int[] array){
createBigHeap(array);//首先我們要將這個陣列變成大堆
int end=array.length-1;
while (end>0){
int temp=array[end];
array[end]=array[0];
array[0]=temp;
shiftDown(array,0,end);
end--;
}
}時間復雜度：O(N*logN)；
空間復雜度：O(1)；
不穩定
六、快速排序
挖坑法
對于快速排序我們一般采用挖坑法來解題
6.1、遞回實作
思路：
挖坑法就是將隊首元素拿出來，從最后一個數向前遍歷找到第一個小于隊首元素的放入挖的坑中填補，在從前向后遍歷找到第一個大于隊首元素的放入又挖的坑中填平，重復上述程序，
代碼實作：
public static int sort(int[] array,int fast,int end){
int temp=array[fast];
while (fast<end){
while (fast<end && temp<=array[end]){
end--;
}
array[fast]=array[end];
while (fast<end && temp>=array[fast]){
fast++;
}
array[end]=array[fast];
}
array[end]=temp;
return end;
}
public static void aSort(int[] array,int left,int right){
if(left>=right){
return;
}
int index=sort(array,left,right);
aSort(array,left,index-1);
aSort(array,index+1,right);
}
public static void qSort(int[] array){
aSort(array,0,array.length-1);
}代碼優化：
1.隨機選擇基準
public static void aSort(int[] array,int left,int right){
if(left>=right){
return;
}
//隨機選擇
Random rand=new Random();
int arr=rand.nextInt(right-left)+left+1;
int temp=array[left];
array[left]=array[arr];
array[arr]=temp;
int index=sort(array,left,right);
aSort(array,left,index-1);
aSort(array,index+1,right);
}2.三數取中法
public static void find(int[] array,int left,int right){
int mid=(left+right)/2;
//array[mid]<=array[left]<=array[right]
if(array[mid]>array[left]){
int temp=array[mid];
array[mid]=array[left];
array[left]=temp;
}
if(array[left]>array[right]){
int temp=array[right];
array[right]=array[left];
array[left]=temp;
}
if(array[mid]>array[right]){
int temp=array[right];
array[right]=array[mid];
array[mid]=temp;
}
}3.插入排序
//插入排序
if((right-left+1)<=100){
insertSort2(array,left,right);
return;//
}6.2、非遞回實作(遍歷實作)
思路：
我們可以通過堆疊先進后出的特性，通過回圈來解題，
代碼實作：
//快排思想
public static int sort(int[] array,int left,int right){
int temp=array[left];
while (left<right){
while (left<right && temp<=array[right]){
right--;
}
array[left]=array[right];
while (left<right && temp>=array[left]){
left++;
}
array[right]=array[left];
}
array[left]=temp;
return left;
}
public static void quickSort(int[] array){
//我們先創建一個堆疊
Stack<Integer> stack=new Stack<>();
//先將頭和尾放進去
stack.push(0);
stack.push(array.length-1);
int left,right;//創建兩個變數對出堆疊的成員進行賦值
while (!stack.isEmpty()){
right=stack.pop();
left=stack.pop();
int index=sort(array,left,right);
//進行判斷放入其他的元素
//必須要保證有兩個或者兩個以上的元素才能添加
if(index>left+1){
stack.push(left);
stack.push(index-1);
}
if(index<right-1){
stack.push(index+1);
stack.push(right);
}
}
}時間復雜度：最好O(N*logN)，最壞O(N^2)；
空間復雜度：最好O(logN),最壞O(N);
不穩定
七、歸并排序
思想：
我們將陣列以二的倍數一步一步進行劃分，當劃分成一個一個之后進行排序，之后向上排序合并，進行排序，
7.1、遞回實作
代碼實作：
public static void bSort(int[] array,int left,int mid,int right){
int[] arr=new int[right-left+1];
int k=0;
int as=left;
int ae=mid;
int ds=mid+1;
int de=right;
while (as<=ae && ds<=de){
if(array[as]<array[ds]){
arr[k++]=array[as++];
}else {
arr[k++]=array[ds++];
}
}
while (as<=ae){
arr[k++]=array[as++];
}
while (ds<=de){
arr[k++]=array[ds++];
}
for(int i=0;i<arr.length;i++){
array[i+left]=arr[i];
}
}
public static void gSort(int[] array,int left,int right){
if(left>=right){
return;
}
//歸
int mid=(left+right)/2;
gSort(array,left,mid);
gSort(array,mid+1,right);
//并
bSort(array,left,mid,right);
}
public static void quickSort(int[] array){
gSort(array,0,array.length-1);
}7.2、非遞回實作(遍歷實作)
代碼實作：
public static void gbSort(int[] array,int gay){
int[] arr=new int[array.length];
int k=0;
int as=0;
int ae=as+gay-1;
int bs=ae+1;
int be=bs+gay-1>=array.length-1?array.length-1:bs+gay-1;//需要判斷be和array的關系
while (bs<array.length){ //說明至少存在兩組
while (as<=ae && bs<=be){
if(array[as]<array[bs]){
arr[k++]=array[as++];
}else{
arr[k++]=array[bs++];
}
}
while (as<=ae){
arr[k++]=array[as++];
}
while (bs<=be){
arr[k++]=array[bs++];
}
as=be+1;
ae=as+gay-1;
bs=ae+1;
be=bs+gay-1>=array.length-1?array.length-1:bs+gay-1;
}
//到這個地方就只有一個
while (as<array.length){
arr[k++]= array[as++];
}
for(int i=0;i<arr.length;i++){
array[i]=arr[i];
}
}
public static void quickSort(int[] array){
for(int i=1;i<array.length;i*=2){
gbSort(array,i);
}
}
時間復雜度：O(N*logN)；
空間復雜度：O(N);
穩定
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330317.html
標籤：其他