Java實(shí)現(xiàn)幾種常見排序算法代碼
穩(wěn)定度(穩(wěn)定性)
一個(gè)排序算法是穩(wěn)定的,就是當(dāng)有兩個(gè)相等記錄的關(guān)鍵字R和S,且在原本的列表中R出現(xiàn)在S之前,在排序過的列表中R也將會(huì)是在S之前。
排序算法分類
常見的有插入(插入排序/希爾排序)、交換(冒泡排序/快速排序)、選擇(選擇排序)、合并(歸并排序)等。
一.插入排序
插入排序(Insertion Sort),它的工作原理是通過構(gòu)建有序序列,對(duì)于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復(fù)把已排序元素逐步向后挪位,為最新元素提供插入空間。
一般來說,插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下:
從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序。
取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描。
如果該元素(已排序)大于新元素,將該元素移到下一位置。
重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置。
將新元素插入到該位置后。
重復(fù)步驟2~5。
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
二.希爾排序
希爾排序(Shell Sort)是插入排序的一種。是針對(duì)直接插入排序算法的改進(jìn)。該方法又稱縮小增量排序,因DL.Shell于1959年提出而得名。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的:
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí), 效率高, 即可以達(dá)到線性排序的效率。
但插入排序一般來說是低效的, 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
三.冒泡排序
冒泡排序(Bubble Sort,臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序算法的運(yùn)作如下:
比較相鄰的元素,如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作,從開始第一對(duì)到結(jié)尾的最后一對(duì),在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 如果一次內(nèi)循環(huán)中發(fā)生了交換,那么繼續(xù)比較;如果一次內(nèi)循環(huán)中沒發(fā)生任何交換,則認(rèn)為已經(jīng)排序好了。
if (!isSort)
break;
}
}
四.快速排序
快速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是:通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
快速排序使用分治法(Divide and conquer)策略來把一個(gè)串行(list)分為兩個(gè)子串行(sub-lists)。
步驟為:
從數(shù)列中挑出一個(gè)元素,稱為 "基準(zhǔn)"(pivot)。
重新排序數(shù)列,所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面,所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后,該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作。
遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
/*
* more efficient implements for quicksort. <br />
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
public class Quicksort {
public static final int CUTOFF = 11;
/**
* quick sort algorithm. <br />
*
* @param arr an array of Comparable items. <br />
*/
public static <T extends Comparable<? super T>> void quicksort(T[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* get the median of the left, center and right. <br />
* order these and hide the pivot by put it the end of of the array. <br />
*
* @param arr an array of Comparable items. <br />
* @param left the most-left index of the subarray. <br />
* @param right the most-right index of the subarray.<br />
* @return T
*/
public static <T extends Comparable<? super T>> T median(T[] arr, int left, int right) {
int center = (left + right) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, left, right);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[right - 1];
}
/**
* internal method to sort the array with quick sort algorithm. <br />
*
* @param arr an array of Comparable Items. <br />
* @param left the left-most index of the subarray. <br />
* @param right the right-most index of the subarray. <br />
*/
private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
if (left + CUTOFF <= right) {
// find the pivot
T pivot = median(arr, left, right);
// start partitioning
int i = left, j = right - 1;
for (;;) {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
if (i < j)
swapRef(arr, i, j);
else
break;
}
// swap the pivot reference back to the small collection.
swapRef(arr, i, right - 1);
quickSort(arr, left, i - 1); // sort the small collection.
quickSort(arr, i + 1, right); // sort the large collection.
} else {
// if the total number is less than CUTOFF we use insertion sort
// instead (cause it much more efficient).
insertionSort(arr, left, right);
}
}
/**
* method to swap references in an array.<br />
*
* @param arr an array of Objects. <br />
* @param idx1 the index of the first element. <br />
* @param idx2 the index of the second element. <br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* method to sort an subarray from start to end with insertion sort
* algorithm. <br />
*
* @param arr an array of Comparable items. <br />
* @param start the begining position. <br />
* @param end the end position. <br />
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray(data);
quicksort(data);
printArray(data);
}
}
五.選擇排序
選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。
因?yàn)槊恳惶舜_定元素的過程中都會(huì)有一個(gè)選擇最小值的子流程,所以人們形象地稱之為選擇排序。
舉個(gè)例子,序列5 8 5 2 9,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了,所以選擇排序不是一個(gè)穩(wěn)定的排序算法。
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; // 無序區(qū)的最小數(shù)據(jù)數(shù)組下標(biāo)
for (int j = i + 1; j < data.length; j++) { // 在無序區(qū)中找到最小數(shù)據(jù)并保存其數(shù)組下標(biāo)
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 如果不是無序區(qū)的最小值位置不是默認(rèn)的第一個(gè)數(shù)據(jù),則交換之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
六.歸并排序
歸并排序(Merge sort)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。
歸并操作的過程如下:
申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來存放合并后的序列。
設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置。
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置。
重復(fù)步驟3直到某一指針達(dá)到序列尾。
將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
public static int[] mergeSort(int[] arr) {// 歸并排序 --遞歸
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 歸并排序子程序
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
完整代碼(除QuickSort)
package com.clzhang.sample.thinking;
import java.util.*;
/**
* 幾路常見的排序算法Java實(shí)現(xiàn)
* @author acer
*
*/
public class CommonSort {
/**
* 插入排序具體算法描述如下:
* 1.從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序
* 2.取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描
* 3.如果該元素(已排序)大于新元素,將該元素移到下一位置
* 4.重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置
* 5.將新元素插入到該位置后
* 6.重復(fù)步驟2~5
*/
public static void insertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
/**
* 希爾排序,算法實(shí)現(xiàn)思想?yún)⒖季S基百科;適合大數(shù)量排序操作。
*/
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h)
Collections.swap(a, j, j-h);
}
/**
* 冒泡排序算法的運(yùn)作如下:
* 1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。
* 2.對(duì)每一對(duì)相鄰元素作同樣的工作,從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn),最后的元素應(yīng)該會(huì)是最大的數(shù)。
* 3.針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。
* 4.持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。[1]
*/
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 如果一次內(nèi)循環(huán)中發(fā)生了交換,那么繼續(xù)比較;如果一次內(nèi)循環(huán)中沒發(fā)生任何交換,則認(rèn)為已經(jīng)排序好了。
if (!isSort)
break;
}
}
/**
* 選擇排序的基本思想是:
* 1.遍歷數(shù)組的過程中,以 i 代表當(dāng)前需要排序的序號(hào),則需要在剩余的 [i+1…n-1] 中找出其中的最小值,
* 2.然后將找到的最小值與 i 指向的值進(jìn)行交換。
* 因?yàn)槊恳惶舜_定元素的過程中都會(huì)有一個(gè)選擇最小值的子流程,所以人們形象地稱之為選擇排序。
* @param data
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; // 無序區(qū)的最小數(shù)據(jù)數(shù)組下標(biāo)
for (int j = i + 1; j < data.length; j++) { // 在無序區(qū)中找到最小數(shù)據(jù)并保存其數(shù)組下標(biāo)
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 如果不是無序區(qū)的最小值位置不是默認(rèn)的第一個(gè)數(shù)據(jù),則交換之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* 歸并操作的過程如下:
* 1.申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來存放合并后的序列
* 2.設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
* 3.比較兩個(gè)指針?biāo)赶虻脑?,選擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置
* 4.重復(fù)步驟3直到某一指針達(dá)到序列尾
* 5.將另一序列剩下的所有元素直接復(fù)制到合并序列尾
*/
public static int[] mergeSort(int[] arr) {// 歸并排序 --遞歸
if (arr.length == 1) {
return arr;
}
int half = arr.length / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 歸并排序子程序
int[] result = new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > arr1.length - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > arr2.length - 1) {
break;
}
}
k++;
}
for (; i < arr1.length; i++) {
result[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
result[++k] = arr2[j];
}
return result;
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
printArray(a);
bubbleSort(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
selectSort(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
insertionSort(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(data[i]);
System.out.println(list);
shellSort(list);
System.out.println(list);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}
相關(guān)文章
java 學(xué)習(xí)筆記(入門篇)_java的安裝與配置
學(xué)習(xí)Java已經(jīng)很長(zhǎng)時(shí)間了,由于基礎(chǔ)不好遇到問題就無從下手,所以,打算寫Java的隨手筆記來鞏固基礎(chǔ),加強(qiáng)學(xué)習(xí),接下來講解java的安裝,配置等,感興趣的朋友可以參考下2013-01-01MyBatis數(shù)據(jù)脫敏的實(shí)現(xiàn)方案介紹
在我們數(shù)據(jù)庫中有些時(shí)候會(huì)保存一些用戶的敏感信息,比如:手機(jī)號(hào)、銀行卡等信息,如果這些信息以明文的方式保存,那么是不安全的2022-08-08SpringBoot+Mybatis實(shí)現(xiàn)登錄注冊(cè)的示例代碼
這篇文章主要介紹了SpringBoot+Mybatis實(shí)現(xiàn)登錄注冊(cè)的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03java面向?qū)ο笤O(shè)計(jì)原則之里氏替換原則示例詳解
這篇文章主要為大家介紹了java面向?qū)ο笤O(shè)計(jì)原則之里氏替換原則示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪2021-10-10SpringCloud OpenFeign超時(shí)控制示例詳解
在Spring Cloud中使用OpenFeign時(shí),可以通過配置來控制請(qǐng)求的超時(shí)時(shí)間,這篇文章主要介紹了SpringCloud OpenFeign超時(shí)控制,需要的朋友可以參考下2024-05-05Java實(shí)現(xiàn)動(dòng)態(tài)代理
本文給大家介紹的是java使用動(dòng)態(tài)代理類實(shí)現(xiàn)動(dòng)態(tài)代理的方法和示例,這里推薦給大家,有需要的小伙伴參考下吧2015-02-02Java實(shí)現(xiàn)批量操作Excel的示例詳解
在操作Excel的場(chǎng)景中,通常會(huì)有一些針對(duì)Excel的批量操作,以GcExcel為例,為大家詳細(xì)介紹一下Java是如何實(shí)現(xiàn)批量操作Excel的,需要的可以參考一下2023-07-07