1. 常見的排序演算法—選擇，冒泡，插入，快速，歸並
太久沒看代碼了，最近打算復習一下java，又突然想到了排序演算法，就把幾種常見的排序演算法用java敲了一遍，這里統一將無序的序列從小到大排列。
選擇排序是一種簡單直觀的排序演算法。它的工作原理是：第一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小元素，繼續放在下一個位置，直到待排序元素個數為0。
選擇排序代碼如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
冒泡排序是一種比較基礎的排序演算法，其思想是相鄰的元素兩兩比較，較大的元素放後面，較小的元素放前面，這樣一次循環下來，最大元素就會歸位，若數組中元素個數為n，則經過（n-1）次後，所有元素就依次從小到大排好序了。整個過程如同氣泡冒起，因此被稱作冒泡排序。
選擇排序代碼如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
插入排序也是一種常見的排序演算法，插入排序的思想是：創建一個與待排序數組等大的數組，每次取出一個待排序數組中的元素，然後將其插入到新數組中合適的位置，使新數組中的元素保持從小到大的順序。
插入排序代碼如下：
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序演算法有大幅提升。因為使用冒泡排序時，一次外循環只能歸位一個值，有n個元素最多就要執行（n-1）次外循環。而使用快速排序時，一次可以將所有元素按大小分成兩堆，也就是平均情況下需要logn輪就可以完成排序。
快速排序的思想是：每趟排序時選出一個基準值（這里以首元素為基準值），然後將所有元素與該基準值比較，並按大小分成左右兩堆，然後遞歸執行該過程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
歸並排序是建立在歸並操作上的一種有效的排序演算法，歸並排序對序列的元素進行逐層折半分組，然後從最小分組開始比較排序，每兩個小分組合並成一個大的分組，逐層進行，最終所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
歸並排序這里我使用了left，right等變數，使其可以通用，並沒有直接用數字表示那麼明確，所以給出相關偽代碼，便於理解。
Mergesort(arr[0...n-1])
//輸入：一個可排序數組arr[0...n-1]
//輸出：非降序排列的數組arr[0...n-1]
if n>1
arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//確保arr_1中元素個數>=arr_2中元素個數
//對於總個數為奇數時，arr_1比arr_2中元素多一個；對於總個數為偶數時，沒有影響
arr[n/2...n-1] to arr_2[0...n/2-1]
Mergesort(arr_1[0...(n+1)/2-1])
Mergesort(arr_2[0...n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
//輸入：兩個有序數組arr_1[0...p-1]和arr_2[0...q-1]
//輸出：將arr_1與arr_2兩數組合並到arr
int i<-0;j<-0;k<-0
while i
<p span="" do<="" jif arr_1[i] <= arr_2[j]
arr[k] <- arr_1[i]
i<-i+1
else arr[k] <- arr_2[j];j<-j+1
k<-k+1
if i=p
arr_2[j...q-1] to arr[k...p+q-1]
else arr_1[i...p-1] to arr[k...p+q-1]
package test_1;
import java.util.Scanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr_1 = new int[10];
for(int i = 0 ; i < 10 ; i++)
arr_1[i] = sc.nextInt();
Sort demo_1 = new Sort();
//1~5一次只能運行一個，若多個同時運行，則只有第一個有效，後面幾個是無效排序。因為第一個運行的已經將帶排序數組排好序。
demo_1.Select_sort(arr_1);//-----------------------1
//demo_1.Bubble_sort(arr_1);//---------------------2
/* //---------------------3
demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
System.out.print("經過快速排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
//demo_1.Insert_sort(arr_1);//--------------------4
/* //--------------------5
demo_1.Mergesort(arr_1,0,arr_1.length - 1);
System.out.print("經過歸並排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("經過選擇排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("經過冒泡排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("經過插入排序後：");
for(int i = 0 ; i < 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有錯誤，麻煩指正，不勝感激。
2. 哪位幫我講講java中的快速排序法
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。最壞情況的時間復雜度為O(n2)，最好情況時間復雜度為O(nlog2n)。
另外 java沒指針概念 可以認為是句柄
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一趟快速排序的演算法是：
1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；
2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；
4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；
5）、重復第3、4步，直到I=J；
例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進行第一次交換後： 27 38 65 97 76 13 49
( 按照演算法的第三步從後面開始找)
進行第二次交換後： 27 38 49 97 76 13 65
( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )
進行第三次交換後： 27 38 13 97 76 49 65
( 按照演算法的第五步將又一次執行演算法的第三步從後開始找)
進行第四次交換後： 27 38 13 49 76 97 65
( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時J：=4 )
此時再執行第三步的時候就發現I=J，從而結束一躺快速排序，那麼經過一躺快速排序之後的結果是：27 38 13 49 76 97 65，即所以大於49的數全部在49的後面，所以小於49的數全部在49的前面。
快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}
分別對前後兩部分進行快速排序 {13} 27 {38}
結束 結束 {49 65} 76 {97}
49 {65} 結束
結束
3. 如何用java實現快速排序，簡答講解下原理
快速排序思想：
通過對數據元素集合Rn 進行一趟排序劃分出獨立的兩個部分。其中一個部分的關鍵字比另一部分的關鍵字小。然後再分別對兩個部分的關鍵字進行一趟排序，直到獨立的元素只有一個，此時整個元素集合有序。
快速排序的過程，對一個元素集合R[ low ... high ] ,首先取一個數（一般是R[low] ）做參照 ， 以R[low]為基準重新排列所有的元素。
所有比R[low]小的放前面，所有比R[low] 大的放後面，然後以R[low]為分界，對R[low ... high] 劃分為兩個子集和，再做劃分。直到low >= high 。
比如：對R={37, 40, 38, 42, 461, 5, 7, 9, 12}進行一趟快速排序的過程如下(注:下面描述的內容中元素下表從 0 開始)：
開始選取基準 base = 37，初始位置下表 low = 0 ， high = 8 ， 從high=8，開始如果R[8] < base , 將high位置中的內容寫入到R[low]中, 將high位置空出來, low = low +1 ;
從low開始探測，由於low=1 ， R[low] > base ,所以將R[low]寫入到R[high] , high = high -1 ;
檢測到low < high ,所以第一趟快速排序仍需繼續:
此時low=1，high=7，因為 R[high] < base ,所以將 R[high] 寫入到到R[low]中,low = low + 1;
從low開始探測,low = 2 , R[low] >base ,所以講R[low]寫入到R[high]，high=high-1;
繼續檢測到 low 小於high
此時low=2，high=6，同理R[high] < base ,將R[high] 寫入到R[low]中，low=low+1;
從low繼續探測,low = 3 , high=6 , R[low] > base , 將R[low]寫入到R[high]中，high = high-1;
繼續探測到low小於high
此時low=3，high=5，同理R[high] < base,將R[high]寫入到R[low]中，low = low +1；
從low繼續探測，low = 4，high=5，由於R[low] > base , 將R[low]寫入到R[high]中，high = high -1 ;
此時探測到low == high == 4 ；該位置即是base所在的位置，將base寫入到該位置中.
然後再對子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一個元素，或沒有元素。
快速排序的Java實現：
private static boolean isEmpty(int[] n) {
return n == null || n.length == 0;
}
// ///////////////////////////////////////////////////
/**
* 快速排序演算法思想——挖坑填數方法：
*
* @param n 待排序的數組
*/
public static void quickSort(int[] n) {
if (isEmpty(n))
return;
quickSort(n, 0, n.length - 1);
}
public static void quickSort(int[] n, int l, int h) {
if (isEmpty(n))
return;
if (l < h) {
int pivot = partion(n, l, h);
quickSort(n, l, pivot - 1);
quickSort(n, pivot + 1, h);
}
}
private static int partion(int[] n, int start, int end) {
int tmp = n[start];
while (start < end) {
while (n[end] >= tmp && start < end)
end--;
if (start < end) {
n[start++] = n[end];
}
while (n[start] < tmp && start < end)
start++;
if (start < end) {
n[end--] = n[start];
}
}
n[start] = tmp;
return start;
}
在代碼中有這樣一個函數：
public static void quickSortSwap(int[] n, int l, int h)
該函數可以實現，元素集合中特定的 l 到 h 位置間的數據元素進行排序。
4. java編程實現隨機數組的快速排序
java編程實現隨機數組的快速排序步驟如下：
1、打開Eclipse，新建一個Java工程，在此工程里新建一拍模個Java類；
2、在新建的類中聲明一個產生隨機數的Random變數，再聲明一個10個長度的int型數組；
3、將產生的隨機數逐個放入到數組中；
4、利用排序演算法對隨機數組進行排序。
具體代碼如下：
importjava.util.Random;
publicclassDemo{
publicstaticvoidmain(String[]args){
intcount=0;
Randomrandom=newRandom();
inta[]襲蘆緩=newint[10];
while(count<10){
a[count]=random.nextInt(1000);//產生0-999的隨機數
count++;
}
for(inti=0;i<a.length-1;i++){
intmin=i;
for(intj=嘩寬i+1;j<a.length;j++){
if(a[j]<a[min]){
min=j;
}
}
if(min!=i){
intb=a[min];
a[min]=a[i];
a[i]=b;
}
}
for(intc=0;c<a.length;c++){
System.out.print(a[c]+"");
}
}
}
5. Java數組排序 幾種排序方法詳細一點
JAVA中在運用數組進行排序功能時，一般有四種方法：快速排序法、冒泡法、選擇排序法、插入排序法。
快速排序法主要是運用了Arrays中的一個方法Arrays.sort（）實現。
冒泡法是運用遍歷數組進行比較，通過不斷的比較將最小值或者最大值一個一個的遍歷出來。
選擇排序法是將數組的第一個數據作為最大或者最小的值，然後通過比較循環，輸出有序的數組。
插入排序是選擇一個數組中的數據，通過不斷的插入比較最後進行排序。下面我就將他們的實現方法一一詳解供大家參考。
<1>利用Arrays帶有的排序方法快速排序
publicclassTest2{
publicstaticvoidmain(String[]args){
int[]a={5,4,2,4,9,1};
Arrays.sort(a);//進行排序
for(inti:a){
System.out.print(i);
}
}
}<2>冒泡排序演算法
publicstaticint[]bubbleSort(int[]args){//冒泡排序演算法
for(inti=0;i<args.length-1;i++){
for(intj=i+1;j<args.length;j++){
if(args[i]>args[j]){
inttemp=args[i];
args[i]=args[j];
args[j]=temp;
}
}
}
returnargs;
}<3>選擇排序演算法
publicstaticint[]selectSort(int[]args){//選擇排序演算法
for(inti=0;i<args.length-1;i++){
intmin=i;
for(intj=i+1;j<args.length;j++){
if(args[min]>args[j]){
min=j;
}
}
if(min!=i){
inttemp=args[i];
args[i]=args[min];
args[min]=temp;
}
}
returnargs;
}<4>插入排序演算法
publicstaticint[]insertSort(int[]args){//插入排序演算法
for(inti=1;i<args.length;i++){
for(intj=i;j>0;j--){
if(args[j]<args[j-1]){
inttemp=args[j-1];
args[j-1]=args[j];
args[j]=temp;
}elsebreak;
}
}
returnargs;
}