常見的七種排序演算法
- 引言
- 1.冒泡排序
- 思路
- 代碼
- 復雜度分析
- 2.插入排序
- 思路
- 代碼
- 復雜度分析
- 3.希爾排序
- 思路
- 代碼
- 復雜度分析
- 4.選擇排序
- 思路
- 代碼
- 復雜度分析
- 5.堆排序
- 思路
- 代碼
- 復雜度分析
- 6.快速插入排序
- 思路
- 代碼
- 復雜度分析
- 7.歸并排序
- 思路
- 代碼
- 復雜度分析
引言
何謂排序?就是使一串記錄,按照其中的某個或某些關鍵字的大小,遞增或遞減的排列起來的操作,平常的背景關系中,如果提到排序,通常指的是排升序,且通常意義上指的都是原地排序.在
《大話資料結構》這本書中將排序演算法分為兩個類別:內排序和外排序,這里我主要介紹內排序的多種方法，
1.冒泡排序
思路
冒泡排序是一種交換排序:在無序區間,兩兩比較相鄰記錄的關鍵字,將最大的數冒泡到無序區間的最后,持續這個程序,直到陣列整體有序，
接下來就按照上面的方法將陣列進行排序，得到七趟排序結果，
代碼
/**
* @author yty
* @version 1.0
* @date 2021-10-04 22:56
* @description:冒泡排序
*/
public class TestSort5 {
public static void bubbleSort(int[] array) {
for (int bound = 0; bound < array.length; bound++) {
//[0，bound]已排序區間
//[bound,size] 待排序區間
for (int cur = array.length - 1; cur > bound; cur--) {
if (array[cur - 1] > array[cur]) {
swap(array, cur - 1, cur);
}
}
}
}
public static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
public static void main (String[]args){
int[] arr = {9, 1, 5, 8, 3, 7, 4, 6, 2};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
復雜度分析
時間復雜度:O(N^2);空間復雜度:O(1);穩定排序
2.插入排序
思路
整個區間被分為有序區間[0,bound],無序區間[bound,size],每次選擇無序區間的第一個元素,在有序區間內選擇合適位置插入
代碼
/**
* @author yty
* @version 1.0
* @date 2021-09-30 23:50
* @description:插入排序演算法
*/
public class TestSort {
//升序排序
public static void insertSort(int[] array){
//通過bound來劃分兩個區間
//[0,bound]已排序區間
//[bound,size]待排序區間
for (int bound = 1; bound < array.length; bound++) {
//bound=1,是因為第一個元素相當于是一個已經排好的陣列
int v=array[bound];
int cur=bound-1;
for (; cur >=0 ; cur--) {
//從排序好的陣列里面最后一個元素往前遍歷比較
if (array[cur] > v){
//與排序區間的后一個值進行比較
array[cur+1]=array[cur];
//把區間之間的大小關系按照升序排列
}else {
//此時說明不用排序了，找到了位置
break;
}
}
array[cur+1]=v;
//更新v的值，繼續進行比較
}
}
public static void main(String[] args) {
int[] arr={9,1,5,8,3,7,4,6,2};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
復雜度分析
時間復雜度:O(N^2);空間復雜度:O(1);穩定排序
3.希爾排序
思路
其實差不多就是進階版的插入排序,先分組,針對每個組進行插入排序,逐漸縮小組的個數,最終組的個數就接近有序了.
代碼
/**
* @author yty
* @version 1.0
* @date 2021-10-03 22:42
* @description:希爾排序演算法
*/
public class TestSort2 {
public static void shellSort(int[] array){
int gap= array.length/2;
while (gap > 1){
//需要回圈進行分組插排
insertSortGap(array,gap);
gap=gap / 2;
}
insertSortGap(array,1);
}
private static void insertSortGap(int[] array, int gap) {
//與插入排序很相似
//通過bound來劃分兩個區間
//[0,bound]已排序區間
//[bound,size]待排序區間
for (int bound = gap; bound < array.length; bound++) {
//bound=gap,此回圈要把所有組都處理完畢
//先處理第一組的第一個元素和第二個元素，在處理第二組的第一個元素和第二個元素，以此類推
int v = array[bound];
int cur = bound - gap;//分組排序就與插排的-1不同了
//即找同組中的數字進行比較
for (; cur >= 0; cur -= gap) {
//找到同組中的相鄰元素，同組元素的下標插值就是gap
if (array[cur] > v) {
//與排序區間的后一個值進行比較
array[cur + gap] = array[cur];
//把區間之間的大小關系按照升序排列
} else {
//此時說明不用排序了，找到了位置
break;
}
}
}
}
}
復雜度分析
時間復雜度:理論極限是O(N ^ 1.3)如果按照size/2,size/4,…1這種方式設定gap序列,此時就是O(N^2);空間復雜度:O(1);穩定性:不穩定,分組的時候可能把相同的值分到不同組中,也就無法保證相對順序
4.選擇排序
思路
基于打擂臺的思想,每次從陣列中找出最小值,然后把最小值放到合適的位置上
代碼
/**
* @author yty
* @version 1.0
* @date 2021-10-03 23:19
* @description:選擇排序演算法
*/
public class TestSort3 {
public static void selectSort(int[] array){
for (int bound=0;bound < array.length;bound++){
//以bound位置的元素作為擂主，回圈從待排序區間取出元素與擂主比較
//如果打擂成功，就與擂主交換
for (int cur=bound+1;cur < array.length;cur++){
if (array[cur] < array[bound]){
int tmp=array[cur];
array[cur]=array[bound];
array[bound]=tmp;
}
}
}
}
}
復雜度分析
時間復雜度:O(N ^ 2);空間復雜度:O(1);穩定性:不穩定排序
5.堆排序
思路
基本原理:選擇排序,只是不再使用遍歷的方式查找無序區間的最大的數,而是通過堆來選擇無序區間的最大的數.如果將陣列按照降序排序:把陣列建立大堆,取出最小值放到另外一個陣列中,回圈取堆頂元素查到新陣列即可;如果將陣列按照升序排序:建立一個大堆,把堆頂元素和堆的最后一個元素互換,把最后一個元素洗掉,再從堆頂向下調整
代碼
/**
* @author yty
* @version 1.0
* @date 2021-10-03 23:27
* @description:堆排序
*/
public class TestSort4 {
public static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
public static void heapSort(int[] array){
//先建立堆
createHeap(array);
//回圈把堆頂元素交換到最后，并調整堆
for (int i = 0; i < array.length; i++) {
//交換堆頂元素和對的最后一個元素
//對俄的元素個數相當于array.length
//堆得最后一個元素下標array.length-1-i
swap(array,0, array.length-1-i);
//交換完成之后，還要把最后一個元素從堆中刪掉
//【0，array.length-1-i】待排序區間
//[array.length-1-i,array.length]已排序區間
shiftDown(array,array.length-1-i,0);
}
}
private static void shiftDown(int[] array, int heapLength, int index) {
int parent=index;
int child=2*parent+1;
while (child < parent){
if (child+1 < heapLength && array[child+1] >array[child]){
child=child+1;
}
if (array[child] > array[parent]){
swap(array,child,parent);
}else {
break;
}
parent=child;
child=2*parent+1;
}
}
private static void createHeap(int[] array) {
for (int i = (array.length-1-1)/2; i >0 ; i--) {
shiftDown(array,array.length,i);
}
}
}
復雜度分析
時間復雜度:O(N * logN);空間復雜度O(1),穩定性:不穩定排序
6.快速插入排序
思路
這里參考遞回的思想簡化代碼:
- 待排序區間中,找到一個基準值(常見的可以取區間的第一個元素或者最后一個元素);
- 以基準值為中心,把整個區間整理成三個部分,左側部分的元素都小于等于基準值,右側部分的元素都大于等于基準值;
- 再次針對左側整理好的區間和右側整理好的區間,進一步進行遞回,重復剛才的整理程序
注意:
1.如果是先從左往右找,再從右往左找,left和right重合位置的元素,一定大于等于基準值,如果是先從右往左找,再從左往右找,left和right重合位置的元素,一定小于等于基準值
2.如果陣列正好反序,此時快排就變成慢排,此時的快速排序效率很低,時間復雜度就是O(N^2)
3.快速排序的效率和基準值取的好壞密切相關.基準值是一個接近陣列中位數的元素.劃分出的左右區間比較均衡.此時效率就比較高.如果當前取到的基準值是最大或者最小值,此時劃分的區間不均衡,效率就低
代碼
/**
* @author yty
* @date 2021-10-05 22:39
* @version 1.0
* @description：快速排序演算法
*/
public class TestSort6 {
//輔助完成遞回程序
//起初為了代碼簡單，區間設定成前閉后閉
public static void quickSort(int[] array){
quickSortHelper(array,0,array.length-1);
}
private static void quickSortHelper(int[] array, int left, int right) {
if (left >= right){
//區間中有0和元素或者一個元素，此時不需要排序
return;
}
//針對[left，right]區間進行調整
// index回傳值就是整理完畢后，left和right的重合位置，知道了這個位置，才能進一步進行遞回
int index=partition(array,left,right);
quickSortHelper(array,left,index-1);
quickSortHelper(array, index+1, right);
}
private static int partition(int[] array, int left, int right) {
int i=left;
int j=right;
int base=array[right];//基準值
while (i < j){
//從左往右找到比基準值大的元素
while (i < j && array[i] <= base){
i++;
}
//當上面的回圈結束是，i要么和j重合，要么i就指向一個大于base的值
//從右往左找比基準值小的元素
while (i < j && array[j] >= base){
j--;
}
//當上面的回圈結束之后，i要么和j重合，要么i就指向一個小于base的值
//交換i 和j 的值
swap(array,i,j);
}
//當i和j重合的時候，最后一步，要把重合位置的元素和基準值進行交換
swap(array,i,right);
//right是陣列中最后一個元素，要求i和j重合的位置必須大于基準值，才能放到最后面
return i;
}
private static void swap(int[] array,int i, int j) {
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
public static void main(String[] args) {
int[] array={8,2,5,4,6,3};
quickSort(array);
System.out.println(Arrays.toString(array));
}
}
復雜度分析
平均時間復雜度:O(N * logN);空間復雜度:O(logN)-O(N):穩定性:不穩定
7.歸并排序
思路
有兩個重要的特點:1.適用于外部排序(資料存在磁盤上);2.適用于鏈表排序.基本思路來源于經典問題:把兩個鏈表合并成一個
代碼
import java.util.Arrays;
/**
* @author yty
* @version 1.0
* @date 2021-10-09 22:19
* @descripition:歸并排序
*/
public class TestSort7 {
public static void merge(int[] array,int low,int mid,int high){
//[low,mid] 有序區間
//[mid,high] 有序區間
//把這兩個有序陣列合并成一個有序陣列
int[] output = new int[high-low];
int outputIndex=0;
int cur1=low;
int cur2=mid;
while(cur1 < mid && cur2 < high){
//這里誰小就把誰返給陣列里面
if (array[cur1] <= array[cur2]){
//穩定排序，<=才能保證穩定性
output[outputIndex]=array[cur1];
outputIndex++;
cur1++;
}else {
output[outputIndex]=array[cur2];
outputIndex++;
cur2++;
}
}
//回圈結束，一個到達結尾，一個還有剩余
//把剩下的拷貝到陣列里
while (cur1 < mid){
output[outputIndex]=array[cur1];
outputIndex++;
cur1++;
}
while (cur2 < high){
output[outputIndex]=array[cur2];
outputIndex++;
cur2++;
}
//最后一步，output的元素搬運到原來的陣列
for (int i = 0; i < high-low; i++) {
array[low+i]=output[i];
}
}
public static void mergeSort(int[] array){
mergeSortHelper(array,0,array.length);
}
//(low,high]前閉后開區間
//兩者插值小于1，區間中就只有1個或0個元素
public static void mergeSortHelper(int[] array, int low, int high) {
if (high-low <= 1){
return;
}
int mid=(low+high) / 2;
mergeSortHelper(array,low,mid);
//執行完，low，high已經排序完
mergeSortHelper(array,mid,high);
//執行完，mid，high已經排序完
//當左右區間已經排序完了，說明左右區間是有序區間了
//接下來針對兩個有序區間進行排序
merge(array,low,mid,high);
}
public static void main(String[] args) {
int[] array={8,2,5,4,6,3};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
}
復雜度分析
時間復雜度:O(N * logN);空間復雜度:O(logN)+O(N):穩定性:穩定
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/389140.html
標籤：java
下一篇：一次性上傳300張圖片引發的思考