Java-五种排序算法实现
前言及准备
这篇我们会介绍比较简单的五种排序算法：插入排序、冒泡排序、快速排序、选择排序、归并排序的原理及Java代码实现。
关于实现，我们先定义算法外的方法：
打印数组方法：
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方法调用：
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);
}
其中的排序方法，下面会一一讲解。
插入排序
解析
数列前面部分视为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。
插入排序
实现
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;
}
}
}
}
冒泡排序
解析
依次比较相邻两元素，若前一元素大于后一元素则交换之，直至最后一个元素即为最大；然后重新从首元素开始重复同样的操作，直至倒数第二个元素即为次大元素；依次类推。如同水中的气泡，依次将最大或最小元素气泡浮出水面。
冒泡排序
实现
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;
}
}
}
}
快速排序
解析
先从数列中取出一个数作为key值；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复第二步，直至各区间只有1个数。
快速排序
实现
用到递归的思想：
private static void quickSort(int[] nums, int beginIndex, int endIndex) {
if (endIndex - beginIndex < 1) {
return;
}
int splitIndex = beginIndex;
int tagNum = nums[beginIndex]; // 数组第一个元素作为基准数
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);
}
选择排序
释义
简单选择排序是每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，属于不稳定排序。
选择排序
实现
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个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
归并排序
实现
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;
}
}
结语
排序算法还有很多，如：基数排序、堆排序、希尔排序、桶排序等。
