Java-五種排序算法實(shí)現(xiàn)
前言及準(zhǔn)備
這篇我們會(huì)介紹比較簡(jiǎn)單的五種排序算法：插入排序、冒泡排序、快速排序、選擇排序、歸并排序的原理及Java代碼實(shí)現(xiàn)。
關(guān)于實(shí)現(xiàn)，我們先定義算法外的方法：
打印數(shù)組方法：
private static void printNums(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (i == nums.length - 1) {
System.out.println(nums[i] + "");
} else {
System.out.print(nums[i] + ",");
}
}
}
main方法調(diào)用：
public static void main(String[] args) {
//插入排序
int[] nums1 = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
insertionSort(nums1);
System.out.print("插入排序:");
printNums(nums1);
//冒泡排序
int[] nums2 = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
bubbleSort(nums2);
System.out.print("冒泡排序:");
printNums(nums2);
//快速排序
int[] nums3 = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
quickSort(nums3, 0, nums3.length - 1);
System.out.print("快速排序:");
printNums(nums3);
//選擇排序
int[] nums4 = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
selectionSort(nums4);
System.out.print("選擇排序:");
printNums(nums4);
//歸并排序
int[] nums5 = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
int[] result = mergeSort(nums5);
System.out.print("歸并排序:");
printNums(result);
}
其中的排序方法，下面會(huì)一一講解。
插入排序
解析
數(shù)列前面部分視為有序，依次將后面的無序數(shù)列元素插入到前面的有序數(shù)列中，初始狀態(tài)有序數(shù)列僅有一個(gè)元素，即首元素。在將無序數(shù)列元素插入有序數(shù)列的過程中，采用了逆序遍歷有序數(shù)列，相較于順序遍歷會(huì)稍顯繁瑣，但當(dāng)數(shù)列本身已近排序狀態(tài)效率會(huì)更高。
實(shí)現(xiàn)
private static void insertionSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[i] > nums[j]) {
int temp = nums[i];
for (int k = i; k > j + 1; k--) {
nums[k] = nums[k - 1];
}
nums[j + 1] = temp;
break;
} else if (j == 0) {
int temp = nums[i];
for (int k = i; k > j; k--) {
nums[k] = nums[k - 1];
}
nums[j] = temp;
break;
}
}
}
}
冒泡排序
解析
依次比較相鄰兩元素，若前一元素大于后一元素則交換之，直至最后一個(gè)元素即為最大；然后重新從首元素開始重復(fù)同樣的操作，直至倒數(shù)第二個(gè)元素即為次大元素；依次類推。如同水中的氣泡，依次將最大或最小元素氣泡浮出水面。
實(shí)現(xiàn)
private static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j + 1];
nums[j + 1] = nums[j];
nums[j] = temp;
}
}
}
}
快速排序
解析
先從數(shù)列中取出一個(gè)數(shù)作為key值；將比這個(gè)數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊；對(duì)左右兩個(gè)小數(shù)列重復(fù)第二步，直至各區(qū)間只有1個(gè)數(shù)。
實(shí)現(xiàn)
用到遞歸的思想：
private static void quickSort(int[] nums, int beginIndex, int endIndex) {
if (endIndex - beginIndex < 1) {
return;
}
int splitIndex = beginIndex;
int tagNum = nums[beginIndex]; // 數(shù)組第一個(gè)元素作為基準(zhǔn)數(shù)
for (int i = beginIndex; i <= endIndex; i++) {
if (nums[i] < tagNum) {
splitIndex++;
int temp = nums[i];
nums[i] = nums[splitIndex];
nums[splitIndex] = temp;
}
}
int temp = nums[splitIndex];
nums[splitIndex] = nums[beginIndex];
nums[beginIndex] = temp;
quickSort(nums, beginIndex, splitIndex);
quickSort(nums, splitIndex + 1, endIndex);
}
選擇排序
釋義
簡(jiǎn)單選擇排序是每一趟從待排序的數(shù)據(jù)元素中選擇最小（或最大）的一個(gè)元素作為首元素，直到所有元素排完為止，屬于不穩(wěn)定排序。
實(shí)現(xiàn)
private static void selectionSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int minIndex = i - 1;
for (int j = i; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
int temp = nums[minIndex];
nums[minIndex] = nums[i - 1];
nums[i - 1] = temp;
}
}
歸并排序
釋義
歸并排序是建立在歸并操作上的一種有效的排序算法，采用分治法。首先考慮下如何將2個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單，只要從比較2個(gè)數(shù)列的第一個(gè)數(shù)，誰小就先取誰，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。
實(shí)現(xiàn)
private static int[] mergeSort(int[] nums) {
if (nums.length <= 1) {
return nums;
} else {
int[] lNums = Arrays.copyOfRange(nums, 0, nums.length / 2);
int[] rNums = Arrays.copyOfRange(nums, nums.length / 2, nums.length);
int[] lNewNums = mergeSort(lNums);
int[] rNewNums = mergeSort(rNums);
int lNewIndex = 0;
int rNewIndex = 0;
int[] result = new int[nums.length];
int resultInsertIndex = 0;
while (lNewIndex < lNewNums.length || rNewIndex < rNewNums.length) {
if (lNewIndex >= lNewNums.length) {
if (rNewIndex < rNewNums.length) {
result[resultInsertIndex] = rNewNums[rNewIndex];
resultInsertIndex++;
rNewIndex++;
}
} else if (rNewIndex >= rNewNums.length) {
result[resultInsertIndex] = lNewNums[lNewIndex];
resultInsertIndex++;
lNewIndex++;
} else if (lNewNums[lNewIndex] > rNewNums[rNewIndex]) {
result[resultInsertIndex] = rNewNums[rNewIndex];
resultInsertIndex++;
rNewIndex++;
} else {
result[resultInsertIndex] = lNewNums[lNewIndex];
resultInsertIndex++;
lNewIndex++;
}
}
return result;
}
}
結(jié)語
排序算法還有很多，如：基數(shù)排序、堆排序、希爾排序、桶排序等。
