Java常用的7大排序算法
Java是一門面向對象編程語言,以下總結了下java中常用的七大排序算法,希望對大家有幫助!
1.插入排序算法
插入排序的基本思想是在遍歷數組的過程中,假設在序號 i 之前的元素即 [0..i-1] 都已經排好序,本趟需要找到 i 對應的元素 x 的正確位置 k ,並且在尋找這個位置 k 的過程中逐個將比較過的元素往後移一位,為元素 x “騰位置”,最後將 k 對應的元素值賦為 x ,一般情況下,插入排序的時間複雜度和空間複雜度分別為 O(n2 ) 和 O(1)。
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortInsert(int[] array){
for(int i=1;i<th;i++){
int temp = array[i];
int j;
for(j=i-1;j >= 0 && temp< array[j]; j--){
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
return array;
}
2.選擇排序算法
選擇排序的基本思想是遍歷數組的過程中,以 i 代表當前需要排序的序號,則需要在剩餘的 [i…n-1] 中找出其中的最小值,然後將找到的最小值與 i 指向的值進行交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程,所以人們形象地稱之為選擇排序。選擇排序的時間複雜度和空間複雜度分別為 O(n2 ) 和 O(1) 。
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortSelect(int[] arr){
for (int i = 0; i < th; i++) {
int miniPost = i;
for (int m = i + 1; m < th; m++) {
if (arr[m] < arr[miniPost]) {
miniPost = m;
}
}
if (arr[i] > arr[miniPost]) {
int temp;
temp = arr[i];
arr[i] = arr[miniPost];
arr[miniPost] = temp;
}
}
return arr;
}
3.冒泡排序算法
冒泡排序是將比較大的數字沉在最下面,較小的浮在上面
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortBubble(int[] array){
int temp;
// 第一層循環:表明比較的次數, 比如 length 個元素,比較次數為 length-1 次(肯定不需和自己比)
for(int i=0;i<th-1;i++){
for (int j = th - 1; j > i; j--) {
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
return array;
}
4.快速排序算法
通過一趟排序將待排記錄分割成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分的關鍵字小,則可以分別對這兩部分記錄繼續進行排序,已達到整個序列有序的目的,本質就是,找一個基位(樞軸,分水嶺,作用是左邊的都比它小,右邊的都比它大。
可隨機,取名base,首先從序列最右邊開始找比base小的.,如果小,換位置,從而base移到剛才右邊(比較時比base小)的位置(記為臨時的high位),這樣base右邊的都比base大。然後,從序列的最左邊開始找比base大的,如果大,換位置,從而base移動到剛才左邊(比較時比base大)的位置(記為臨時的low位),這樣base左邊的都比base小,循環以上兩步,直到 low == heigh, 這使才真正的找到了樞軸,分水嶺. 返回這個位置,分水嶺左邊和右邊的序列,分別再來遞歸。
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortQuick(int[] array){
return quickSort(array, 0, th-1);
}
private 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 int partition(int[] arr, int low, int heigh) {
int base = arr[low]; //用子表的第一個記錄做樞軸(分水嶺)記錄
while (low < heigh) { //從表的兩端交替向中間掃描
while (low < heigh && arr[heigh] >= base) {
heigh--;
}
// base 賦值給 當前 heigh 位,base 挪到(互換)到了這裏,heigh位右邊的都比base大
swap(arr, heigh, low);
while (low < heigh && arr[low] <= base) {
low++;
}
// 遇到左邊比base值大的了,換位置
swap(arr, heigh, low);
}
// now low = heigh;
return low;
}
private void swap(int[] arr, int a, int b) {
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
5.合併排序算法
歸併排序採用的是遞歸來實現,屬於“分而治之”,將目標數組從中間一分為二,之後分別對這兩個數組進行排序,排序完畢之後再將排好序的兩個數組“歸併”到一起,歸併排序最重要的也就是這個“歸併”的過程,歸併的過程中需要額外的跟需要歸併的兩個數組長度一致的空間
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
private int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左邊
sort(nums, low, mid);
// 右邊
sort(nums, mid + 1, high);
// 左右歸併
merge(nums, low, mid, high);
}
return nums;
}
private void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數先移到新數組中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左邊剩餘的數移入數組
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右邊邊剩餘的數移入數組
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新數組中的數覆蓋nums數組
for (int k2 = 0; k2 < th; k2++) {
nums[k2 + low] = temp[k2];
}
}
public int[] sortMerge(int[] array) {
return sort(array, 0, th - 1);
}
6.希爾排序算法
希爾排序的誕生是由於插入排序在處理大規模數組的時候會遇到需要移動太多元素的問題。希爾排序的思想是將一個大的數組“分而治之”,劃分為若干個小的數組。
以 gap 來劃分,比如數組 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 來劃分,可以分為 [1, 3, 5, 7] 和 [2, 4, 6, 8] 兩個數組(對應的,如 gap = 3 , 則劃分的數組為: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然後分別對劃分出來的數組進行插入排序,待各個子數組排序完畢之後再減小 gap 值重複進行之前的步驟,直至 gap = 1 ,即對整個數組進行插入排序。
此時的數組已經基本上快排好序了,所以需要移動的元素會很小很小,解決了插入排序在處理大規模數組時較多移動次數的問題,希爾排序是插入排序的改進版,在數據量大的時候對效率的提升幫助很大,數據量小的時候建議直接使用插入排序就好了。
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortShell(int[] array) {
// 取增量
int step = th / 2;
while (step >= 1) {
for (int i = step; i < th; i++) {
int temp = array[i];
int j = 0;
// 跟插入排序的區別就在這裏
for (j = i - step; j >= 0 && temp < array[j]; j -= step) {
array[j + step] = array[j];
}
array[j + step] = temp;
}
step /= 2;
}
return array;
}
7.堆排序算法
本質就是先構造一個大頂堆,parent比children大,root節點就是最大的節點 把最大的節點(root)與尾節點(最後一個節點,比較小)位置互換,剩下最後的尾節點,現在最大,其餘的,從第一個元素開始到尾節點前一位,構造大頂堆遞歸。
/**
* @param int[] 未排序數組
* @return int[] 排完序數組
*/
public int[] sortHeap(int[] array) {
buildHeap(array);// 構建堆
int n = th;
int i = 0;
for (i = n - 1; i >= 1; i--) {
swap(array, 0, i);
heapify(array, 0, i);
}
return array;
}
private void buildHeap(int[] array) {
int n = th;// 數組中元素的個數
for (int i = n / 2 - 1; i >= 0; i--)
heapify(array, i, n);
}
private void heapify(int[] A, int idx, int max) {
int left = 2 * idx + 1;// 左孩子的下標(如果存在的話)
int right = 2 * idx + 2;// 左孩子的下標(如果存在的話)
int largest = 0;// 尋找3個節點中最大值節點的下標
if (left < max && A[left] > A[idx])
largest = left;
else
largest = idx;
if (right < max && A[right] > A[largest])
largest = right;
if (largest != idx) {
swap(A, largest, idx);
heapify(A, largest, max);
}
}
}
// 建堆函數,認為【s,m】中只有 s
// 對應的關鍵字未滿足大頂堆定義,通過調整使【s,m】成為大頂堆=====================================================
public static void heapAdjust(int[] array, int s, int m) {
// 用0下標元素作為暫存單元
array[0] = array[s];
// 沿孩子較大的結點向下篩選
for (int j = 2 * s; j <= m; j *= 2) {
// 保證j為較大孩子結點的下標,j < m 保證 j+1 <= m ,不越界
if (j < m && array[j] < array[j + 1]) {
j++;
}
if (!(array[0] < array[j])) {
break;
}
// 若S位較小,應將較大孩子上移
array[s] = array[j];
// 較大孩子的值變成S位的較小值,可能引起頂堆的不平衡,故對其所在的堆進行篩選
s = j;
}
// 若S位較大,則值不變;否則,S位向下移動至2*s、4*s、。。。
array[s] = array[0];
-
如何使用java
Java是一種可以撰寫跨平台應用程序的面向對象的`程序設計語言。以下是小編為大家搜索整理的如何使用java,希望能給大家帶來幫助!更多精彩內容請及時關注我們應屆畢業生考試網!...
-
2017上半年計算機二級Java備考練習題及答案
練習做多了自然會形成自己的做題方法和速度,為此,今天本站小編為大家整理了以下2017上半年計算機二級Java備考練習題及答案,希望對大家有幫助!練習題一1、以下不是Java中有效的關鍵字。A、constB、NULLC、falseD、this本題考查的是Java的關鍵字。Java中常量null,fa...
-
2017上半年計算機二級Java練習題及答案
計算機等級證書是我們找工作的敲門磚,現在越來越多人重視計算機等級考試。下面是本站小編為大家帶來的2017上半年計算機二級Java練習題及答案,希望對大家的學習有幫助!一、單選題1、結構化程序設計主要強調的是______。A、程序的規模B、程序的易讀性C、程序的執...
-
java中反射機制
導語:Java是一門面向對象編程語言,不僅吸收了C++語言的各種優點,還摒棄了C++裏難以理解的多繼承、指針等概念,因此Java語言具有功能強大和簡單易用兩個特徵。下面我們來看看java中反射機制,希望對大家有所幫助。Java中什麼是反射機制:(JavaReflactioninaction)Java反射...