本文主要介紹Java的七種常見排序算法的實(shí)現(xiàn)脸爱，對(duì)選擇排序遇汞、插入排序、冒泡排序簿废、歸并排序空入、快速排序、希爾排序族檬、最小堆排序進(jìn)行原理分析與實(shí)例介紹歪赢，下面一起來看一下吧：
一、選擇排序(SelectSort)
基本原理：對(duì)于給定的一組記錄单料，經(jīng)過第一輪比較后得到最小的記錄埋凯，然后將該記錄與第一個(gè)記錄的位置進(jìn)行交換；接著對(duì)不包括第一個(gè)記錄以外的其他記錄進(jìn)行第二次比較扫尖，得到最小的記錄并與第二個(gè)記錄進(jìn)行位置交換白对；重復(fù)該過程，直到進(jìn)行比較的記錄只有一個(gè)為止换怖。
public class SelectSort {
public static void selectSort(int[] array) {
int i;
int j;
int temp;
int flag;
for (i = 0; i < array.length; i++) {
temp = array[i];
flag = i;
for (j = i + 1; j < array.length; j++) {
if (array[j] < temp) {
temp = array[j];
flag = j;
}
}
if (flag != i) {
array[flag] = array[i];
array[i] = temp;
}
}
}
public static void main(String[] args) {
int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };
selectSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
二甩恼、插入排序(InsertSort)
基本原理：對(duì)于給定的一組數(shù)據(jù)，初始時(shí)假設(shè)第一個(gè)記錄自成一個(gè)有序序列，其余記錄為無序序列条摸。接著從第二個(gè)記錄開始悦污，按照記錄的大小依次將當(dāng)前處理的記錄插入到其之前的有序序列中，直至最后一個(gè)記錄插入到有序序列中為止钉蒲。
public class InsertSort {
public static void insertSort(int[] a) {
if (a != null) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
int j = i;
if (a[j - 1] > temp) {
while (j >= 1 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
}
a[j] = temp;
}
}
}
int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };
// int[] a =null;
insertSort(a);
}
}
}
三塞关、冒泡排序(BubbleSort)
基本原理：對(duì)于給定的n個(gè)記錄，從第一個(gè)記錄開始依次對(duì)相鄰的兩個(gè)記錄進(jìn)行比較子巾，當(dāng)前面的記錄大于后面的記錄時(shí)帆赢，交換位置，進(jìn)行一輪比較和換位后线梗，n個(gè)記錄中的最大記錄將位于第n位椰于；然后對(duì)前(n-1)個(gè)記錄進(jìn)行第二輪比較；重復(fù)該過程直到進(jìn)行比較的記錄只剩下一個(gè)為止仪搔。
public class BubbleSort {
public static void bubbleSort(int array[]) {
int temp = 0;
int n = array.length;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int a[] = { 45, 1, 21, 17, 69, 99, 32 };
bubbleSort(a);
}
}
}
四瘾婿、歸并排序(MergeSort)
基本原理：利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表，再對(duì)半子表排序烤咧，最后再用遞歸方法將排好序的半子表合并成為越來越大的有序序列偏陪。對(duì)于給定的一組記錄(假設(shè)共有n個(gè)記錄)，首先將每?jī)蓚€(gè)相鄰的長(zhǎng)度為1的子序列進(jìn)行歸并煮嫌，得到n/2(向上取整)個(gè)長(zhǎng)度為2或1的有序子序列笛谦，再將其兩兩歸并，反復(fù)執(zhí)行此過程昌阿，直到得到一個(gè)有序序列饥脑。
public class MergeSort {
public static void merge(int array[], int p, int q, int r) {
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0, k = p; i < n1; i++, k++)
L[i] = array[k];
for (i = 0, k = q + 1; i < n2; i++, k++)
R[i] = array[k];
for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
if (L[i] > R[j]) {
array[k] = L[i];
i++;
} else {
array[k] = R[j];
j++;
}
}
if (i < n1) {
for (j = i; j < n1; j++, k++)
array[k] = L[j];
}
if (j < n2) {
for (i = j; i < n2; i++, k++) {
array[k] = R[i];
}
}
}
public static void mergeSort(int array[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(array, p, q);
mergeSort(array, q + 1, r);
merge(array, p, q, r);
}
}
int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
mergeSort(a, 0, a.length - 1);
for (int j = 0; j < a.length; j++) {
System.out.print(a[j] + " ");
}
}
}
五、快速排序(QuickSort)
基本原理：對(duì)于一組給定的記錄懦冰，通過一趟排序后灶轰，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小刷钢，然后再依次對(duì)前后兩部分的記錄進(jìn)行快速排序笋颤，遞歸該過程，直到序列中的所有記錄均有序?yàn)橹埂?/p>
public class QuickSort {
public static void sort(int array[], int low, int high) {
int i, j;
int index;
if (low >= high)
return;
i = low;
j = high;
index = array[i];
while (i < j) {
while (i < j && index <= array[j])
j--;
if (i < j)
array[i++] = array[j];
while (i < j && index > array[i])
i++;
if (i < j)
array[j--] = array[i];
}
array[i] = index;
sort(array, low, i - 1);
sort(array, i + 1, high);
}
public static void quickSort(int array[]) {
sort(array, 0, array.length - 1);
}
int a[] = { 5, 8, 4, 6, 7, 1, 3, 9, 2 };
quickSort(a);
}
}
}
六内地、希爾排序(ShellSort)
基本原理：先將待排序的數(shù)組元素分成多個(gè)子序列伴澄，使得每個(gè)子序列的元素個(gè)數(shù)相對(duì)減少，然后對(duì)各個(gè)子序列分別進(jìn)行直接插入排序瓤鼻，待整個(gè)待排序序列"基本有序后"秉版，最后再對(duì)所有元素進(jìn)行一次直接插入排序。
public class ShellSort {
public static void shellSort(int[] a) {
int len = a.length;
int i, j;
int h;
int temp;
for (h = len / 2; h > 0; h = h / 2) {
for (i = h; i < len; i++) {
temp = a[i];
for (j = i - h; j >= 0; j -= h) {
if (temp < a[j]) {
a[j + h] = a[j];
} else
break;
}
a[j + h] = temp;
}
}
}
int a[] = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
shellSort(a);
}
}
}
七茬祷、最小堆排序(MinHeapSort)
基本原理：對(duì)于給定的n個(gè)記錄清焕，初始時(shí)把這些記錄看作一顆順序存儲(chǔ)的二叉樹，然后將其調(diào)整為一個(gè)小頂堆，然后將堆的最后一個(gè)元素與堆頂元素進(jìn)行交換后秸妥，堆的最后一個(gè)元素即為最小記錄滚停；接著講前(n-1)個(gè)元素重新調(diào)整為一個(gè)小頂堆，再將堆頂元素與當(dāng)前堆的最后一個(gè)元素進(jìn)行交換后得到次小的記錄粥惧，重復(fù)該過程直到調(diào)整的堆中只剩一個(gè)元素時(shí)為止键畴，該元素即為最大記錄，此時(shí)可得到一個(gè)有序序列突雪。
public class MinHeapSort {
public static void adjustMinHeap(int[] a, int pos, int len) {
int temp;
int child;
for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) {
child = 2 * pos + 1;
if (child < len && a[child] > a[child + 1])
child++;
if (a[child] < temp)
a[pos] = a[child];
else
break;
}
a[pos] = temp;
}
public static void myMinHeapSort(int[] array) {
int i;
int len = array.length;
for (i = len / 2 - 1; i >= 0; i--) {
adjustMinHeap(array, i, len - 1);
}
for (i = len - 1; i >= 0; i--) {
int tmp = array[0];
array[0] = array[i];
array[i] = tmp;
adjustMinHeap(array, 0, i - 1);
}
}
int[] a = { 5, 4, 9, 8, 7, 6, 0, 1, 3, 2 };
myMinHeapSort(a);
}
}
}
?為了讓學(xué)習(xí)變得輕松起惕、高效，今天給大家免費(fèi)分享一套Java教學(xué)資源咏删。幫助大家在成為Java架構(gòu)師的道路上披荊斬棘惹想。需要資料的歡迎加入學(xué)習(xí)交流群：9285，05736
