一、冒泡排序
思想：重復走訪過要排序的序列，一次比較兩個元素，如果他們的順序錯誤就將他們進行交換，一次冒上來的是最小的，其次是第二小。
時間復雜度：O(n^2)
空間復雜度:O(1)
穩定性：穩定
1.
/**
* 冒泡排序
* @param disOrderArray
* @return
*/
public static int[] BubbleSort(int[] disOrderArray) {
int temp;
// 第一層循環:表明比較的次數, 比如 length 個元素,比較次數為 length-1 次（肯定不需和自己比）
for(int i=0;ii;j--)
{
//此處為<時其返回是從小到大排序，>時其返回從大到小
if(disOrderArray[j] < disOrderArray[j-1])
{
temp = disOrderArray[j];
disOrderArray[j] = disOrderArray[j-1];
disOrderArray[j-1] = temp;
}
}
}
return disOrderArray;
}
思想：通過一趟排序將待排記錄分割成兩個部分，其中一部分記錄關鍵字均比另一部分記錄的關鍵字小，則可以分別對這兩部分關鍵字繼續排序，以達到整個序列有序的目的。
時間復雜度：O(nlogn),最壞的情況下為O(n^2)
空間復雜度：O(1)
穩定性:不穩定
/*
*
* 快速排序
*
* 思想:
* 通過一趟排序將待排記錄分割成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,
* 則可以分別對這兩部分記錄繼續進行排序,已達到整個序列有序的目的
*
* 本質就是,找一個基位(樞軸,分水嶺,作用是左邊的都比它小,右邊的都比它大.可隨機,取名base
* 首先從序列最右邊開始找比base小的
* ,如果小,換位置,從而base移到剛才右邊(比較時比base小)的位置(記為臨時的high位),這樣base右邊的都比base大
* 然後,從序列的最左邊開始找比base大的
* ,如果大,換位置,從而base移動到剛才左邊(比較時比base大)的位置(記為臨時的low位),這樣base左邊的都比base小
*
* 循環以上兩步,直到 low == heigh, 這使才真正的找到了樞軸,分水嶺. 返回這個位置,分水嶺左邊和右邊的序列,分別再來遞歸
*/
public static int[] quickSort(int[] arr, int low, int heigh) {
if(low < heigh)
{
int division = partition(arr, low, heigh);
quickSort(arr, low, division - 1);
quickSort(arr, division + 1, heigh);
}
return arr;
}
// 分水嶺,基位,左邊的都比這個位置小,右邊的都大
private static int partition(int[] arr, int low, int heigh) {
int base = arr[low]; //用子表的第一個記錄做樞軸(分水嶺)記錄
while (low < heigh)
{
//更改下面兩個while循環中的<=和>=，即可獲取到從大到小排列
//從表的兩端交替向中間掃描，從小到大排列
while (low < heigh && arr[heigh] >= base)
{
heigh--;
}
// 如果高位小於base,base 賦值給 當前 heigh 位,base 挪到(互換)到了這裡,heigh位右邊的都比base大
swap(arr, heigh, low);
while(low < heigh && arr[low] <= base)
{
low++;
}
// 如果低位大有base,
swap(arr, heigh, low);
}
//現在low=heigh
return low;
}
//交換大小
private static void swap(int[] arr, int heigh, int low) {
int temp = arr[heigh];
arr[heigh] = arr[low];
arr[low] = temp;
}
思想：每一趟排序將會選擇出最小的(或者最大的)值，順序放在已排好序的數列的後面
時間復雜度：O(n^2)
空間復雜度：O(1)
穩定性：不穩定
/**
* 直接選擇排序
* 直接選擇排序每一趟選擇出最小的值
* @param arr
* @return
*/
public static int[] selectionSort(int[] arr) {
for(int i=0;i arr[j])
{
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}
思想：堆排序利用這種堆這種數據結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素
時間復雜度：O(nlogn)
空間復雜度：O(1)
穩定性：不穩定
/**
* 堆排序
* 堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法，可以利用數組的特點快速定位指定索引的元素。
* @param arr
* @return
*/
public static int[] heapSort(int[] arr) {
int i;
// 將arr構成一個大頂堆
// 從 0 到 arr.length/2 ,這些都是有孩子的節點
// 沒孩子的節點構造大頂堆就無意義了
for (i = arr.length / 2; i >= 0; i--)
{
heapAdjust(arr, i, arr.length - 1);
}
for (i = arr.length - 1; i > 0; i--)
{
swap(arr, 0, i);
// 將arr[0...i-1] 重新構造成一個大頂堆
heapAdjust(arr, 0, i - 1);
}
return arr;
}
private static void heapAdjust(int[] arr, int s, int m) {
int temp, j;
temp = arr[s]; // 指向臨時(相對與root節點)的根節點
for (j = 2 * s; j <= m; j *= 2)
{
// 如果右節點比左節點大,當前節點移到右節點
if (j < m && arr[j] < arr[j + 1])
{
// 指向右節點
j++;
}
// 當前的父節點大於現在指向的節點
// 不需要做任何處理
if (temp >= arr[j])
{
break;
}
// 當前的父節點小於其下的子節點
// 換位置,把這個子節點替換到父節點
// 當前這個位置,如果是葉子節點,則它應該是最小的(相對於它的祖先們)
// 這個方法目的就是交換parent與children的值,構造大根堆
// 執行到這裡表明當前節點的父節點(臨時根節點小於當前的節點),
// 把當前節點移到上面,換位置
// arr[s]被覆蓋無所謂,因為temp記了這個值(原來的根節點(相對的parent))
arr[s] = arr[j];
// 現在把當前的這個元素,看做是臨時的parent節點
// 為了找到此時這個元素的孩子節點,看看是否有比當前這個值還大的
// 最後s指向 當前遍歷到的這個元素
s = j;
}
arr[s] = temp;
}
五、插入排序
思想：將一個記錄插入到一個已排好序的有序表中，從而得到一個新的、記錄增1的有序表。默認將第一個元素看為有序表，然後依次插入後邊的元素
時間復雜度：O(n^2)
空間復雜度：O(1)
穩定性：穩定
/**
* 插入排序
* 思想:將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表，
* 默認將第一個元素看為有序表，一次插入後邊的所欲元素
* 時間復雜度O(n^2)
* 空間復雜度O(1) 適用於記錄數量小的
* @param arr
* @return
*/
public static int[] InsertSort(int[] arr) {
//從小到大排列
for(int i=1;i=0 && temp < arr[j];j--)
{
//待插入元素小於已有的，就將已有往後挪，直到元素大於插入元素或已經到序列最首端了
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
return arr;
}
思想：折半插入排序是基於直接插入排序進行改寫的，其可以減少"移動"和"比較"的次數
時間復雜度：O(n^2)
空間復雜度：O(1)
穩定性：穩定
/**
* 折半插入排序
* 優點:可以減少"比較"和"移動"的次數
* @param arr
* @return
*/
public static int[] BInsertSort(int[] arr){
for(int i=1;i=high+1;j--)
{
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
return arr;
}
思想：希爾排序也是插入排序的一種，是直接針對插入排序進行改進的，該方法又稱為"縮小增量排序"。
時間復雜度：O(n^2)
空間復雜度：O(1)
穩定性：不穩定
/**
* 希爾排序(縮小增量排序)
* 希爾排序也是插入排序的一種，只是其有增量，而且最後一次增量必須為1
* @param arr
* @return
*/
public static int[] ShellInsert(int[] arr){
int step = arr.length/2; //取增量
//保證最後一個增量為1
while(step >= 1)
{
for(int i=step;i=0 && temp
八、歸並排序
思想：歸並排序是將兩個或兩個以上的有序表組合成一個有序表，該算法是采用分治法實現
時間復雜度：O(nlogn)
空間復雜度：O(n)
穩定性：穩定
/**
* 歸並排序
* 歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表
* 時間復雜度 O(nlog2n)
* @param arr
* @param tempArray
* @param left
* @param right
* @return
*/
public static int[] mergeSort(int[] arr, int left,int right) {
if (left < right)
{
// 取分割位置
int middle = (left + right) / 2;
// 遞歸劃分數組左序列
mergeSort(arr, left, middle);
// 遞歸劃分數組右序列
mergeSort(arr, middle+1, right);
//將左數組和右數組進行歸並
Merge(arr, left, middle, right);
}
return arr;
}
private static void Merge(int[] arr, int left, int middle,int right) {
int[] tempArray = new int[arr.length];
int leftEnd = middle;
int rightStart = middle+1;
// 臨時數組的下標
int tempIndex = left;
int tmp = left;
// 先循環兩個區間段都沒有結束的情況
while ((left <= leftEnd) && (rightStart <= right))
{
// 左邊的比右邊的小,先插入左邊的
if (arr[left] < arr[rightStart])
{
tempArray[tempIndex++] = arr[left++];
}
else
{
tempArray[tempIndex++] = arr[rightStart++];
}
}
// 判斷左序列是否結束
while (left <= leftEnd)
{
tempArray[tempIndex++] = arr[left++];
}
// 判斷右序列是否結束
while (rightStart <= right)
{
tempArray[tempIndex++] = arr[rightStart++];
}
// 將臨時數組中的內容拷貝回原數組中
// （原left-right范圍的內容被復制回原數組）
while (tmp <= right) {
arr[tmp] = tempArray[tmp++];
}
}
九、基數排序
思想：基數是按照低位先排序，然後收集；再按高位排序，然後再收集，依次類推，直到最高位。
注:表示關鍵詞分類到radix(基數)個盒子，在關鍵詞為數字時，基數為10，當關鍵詞為字母時，基數為26
時間復雜度：O(n+d)
空間復雜度：O(n)
穩定性：穩定
/**
* 基數排序
* @radix 基數 表示 按關鍵詞分類到radix(基數)個盒子 在關鍵詞為數字時，基數為10
* @d 排序元素的位數
* @return
*/
public static int[] RadixSort(int[] arr, int radix, int d){
//用於暫存元素
int[] temp = new int[arr.length];
//用於計數排序
int[] count = new int[radix];
int divide = 1;
for(int i=0;i=0;j--)
{
int tempKey = (temp[j]/divide)%radix;
count[tempKey]--;
arr[count[tempKey]] = temp[j];
}
divide = divide * radix;
}
return arr;
}
public static void main(String[] args) {
//基礎默認從小到大排列
// int[] disOrderArray = {3,1,5,7,0};
//冒泡排序
// disOrderArray = BubbleSort(disOrderArray);
//快速排序
// disOrderArray = quickSort(disOrderArray, 0, disOrderArray.length-1);
//直接選擇排序
// disOrderArray = selectionSort(disOrderArray);
//堆排序
// disOrderArray = heapSort(disOrderArray);
//直接插入排序
// disOrderArray = InsertSort(disOrderArray);
//折半插入排序(二分查找排序)
// disOrderArray = BInsertSort(disOrderArray);
//希爾排序
// disOrderArray = ShellInsert(disOrderArray);
//歸並排序
// disOrderArray = mergeSort(disOrderArray, 0, disOrderArray.length-1);
//基數排序
int[] disOrderArray = {3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
disOrderArray = RadixSort(disOrderArray, 10, 7);
for(int i=0;i
數據結構基本的排序算法基本都全了。
添加一個二分查找算法：類似於折半查找算法
時間復雜度：O(logn)
/**
* 二分查找
* @param arr
* @param searchnum 待查找元素
* @return
*/
public static int BSearch(int[] arr, int searchnum){
int low = 0;
int high = arr.length-1;
while(low<=high)
{
int m = (low+high)/2;
if(searchnum == arr[m])
{
return m;
}
else if(searchnum < arr[m])
{
high = m-1;
}
else
{
low = m+1;
}
}
return -1;
}
