常见算法题目5 -常见的排序算法

常见算法题目5 -常见的排序算法

本文介绍常见的排序算法的思路及代码实现(都是按照从小到大排列)，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

1.冒泡排序

• 思路：重复遍历数组，依次比较相邻元素，若顺序错误则交换，直至没有交换发生。每次外层循环后，最大的都会移动到数组末尾，就像冒水泡一样(水泡由水底往上升起的过程中原来越大)，故称为冒泡排序。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 实现代码：

/**
* 常见的排序算法(从小到大排列) 之 冒泡排序
* @param arr
*/
public static void bubbleSort1(int[] arr) {
for (int i = 0; i < arr.length – 1; i++) {
for (int j = 0; j < arr.length – 1 – i; j++) {
// 比较相邻元素 前>后 则交换位置
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// 为了直观的显现冒泡的过程，可以在这里打下输出
System.out.println("冒泡排序，第" + (i + 1) + "轮排序后，：" + Arrays.toString(arr));
}
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr1 = {7, 6, 5, 4, 3, 2, 1};
System.out.println("原数组：" + Arrays.toString(arr1));
bubbleSort1(arr1);
System.out.println("冒泡排序后：" + Arrays.toString(arr1));
}

2. 选择排序

• 思路：每次从未排序部分选择最小元素，与未排序部分的第一个元素交换。每次外层循环结束后，最小的元素都会一步步移动到数据的前面。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定。与冒泡排序相比都涉及数据位置交换，但涉及相同数值数据的交换，会改变相同数值的相对位置，因此不稳定。但冒泡排序在进行等值判断后不会进行位置交换，故稳定。
• 实现代码：

/**
* 常见的排序算法(从小到大排列) 之 选择排序
* @param arr
*/
public static void testSelectionSort2(int[] arr) {
// 遍历比较
for (int i = 0; i < arr.length – 1; i++) {
// 存储最小值下标索引
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换位置
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 为了直观的显现选择排序的过程，可以在这里打下输出
System.out.println("选择排序，第" + (i + 1) + "轮排序后，：" + Arrays.toString(arr));
}
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr2 = {7, 6, 5, 4, 3, 2, 1};
System.out.println("原数组：" + Arrays.toString(arr2));
testSelectionSort2(arr2);
System.out.println("选择排序后：" + Arrays.toString(arr2));
}

3. 插入排序

• 思路：将数组分为已排序部分和未排序部分，已排序部分为已排序的元素，未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 实现代码：

/**
* 常见的排序算法(从小到大排列) 之 插入排序
* @param arr
*/
public static void insertSort3(int[] arr) {
// 循环判断
for (int i = 1; i < arr.length; i++) {
// 存储当前元素
int temp = arr[i];
// 循环判断，找到插入的位置
int j = i – 1;
// 已排序部分的元素，找到插入的位置
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j—;
}
// 当前循环下标位置数据赋值
arr[j + 1] = temp;
// 为了直观的显现插入排序的过程，可以在这里打下输出
System.out.println("插入排序，第" + i + "轮排序后，：" + Arrays.toString(arr));
}
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr3 = {7, 6, 5, 4, 3, 2, 1};
System.out.println("原数组：" + Arrays.toString(arr3));
insertSort3(arr3);
System.out.println("插入排序后：" + Arrays.toString(arr3));
}

4. 快速排序

• 思路：将数组分为已排序部分和未排序部分，已排序部分为已排序的元素，未排序部分为未排序的元素。将未排序部分中的每一个元素逐个插入到已排序部分的正确位置。 ①选择基准元素：一般选择第一个或最后一个元素作为基准元素。 ②数组分区：比基准元素小的在基准元素的左边，比基准元素大的在基准元素的右边 ③递归：递归对基准元素左边和右边的部分进行快速排序
• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)
• 稳定性：不稳定
• 实现代码：

/**
* 常见的排序算法 之 快速排序(从小到大排列)
* @param arr
*/
public static void quickSort4(int[] arr, int left, int right) {
if (left < right) {
int baseIndex = partition(arr, left, right);
// 递归对基准元素左边和右边的进行快速排序
quickSort4(arr, left, baseIndex – 1);
quickSort4(arr, baseIndex + 1, right);}
}

/**
* 获取基准原始位置
* @param arr
* @param left
* @param right
* @return
*/
private static int partition(int[] arr, int left, int right) {
// 选择最后一个元素为基准元素
int baseValue = arr[right];
int i = left – 1;
for (int j = left; j < right; j++) {
// 当前元素小于基准元素
if (arr[j] < baseValue) {
// 交换位置
i++;
// 交换当前元素与较小元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
System.out.println("快速排序，排序中间过程结果：" + Arrays.toString(arr));
}
// 交换基准元素与较小元素索引下一个元素
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
System.out.println("快速排序，基准元素交换位置后结果：" + Arrays.toString(arr));
// 返回基准元素索引
return i + 1;
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr4 = {5, 6, 2, 3, 1, 7, 4};
System.out.println("原数组：" + Arrays.toString(arr4));
quickSort4(arr4, 0, arr4.length – 1);
System.out.println("快速排序后：" + Arrays.toString(arr4));
}

5.归并排序

• 思路：归并排序是一种典型的分治算法。 ①分：将数组分成两半； ②治：递归对左右两部分进行排序； ③合：将左右两部分有序数组合并为有序数组。
• 时间复杂度：O(nlog n)
• 空间复杂度：O(n)
• 稳定性：稳定
• 实现代码：

/**
* 常见的排序算法 之 归并排序(从小到大排列)
* @param arr
*/
public static void mergeSort5(int[] arr, int left, int right, int[] temp) {
if (arr == null || arr.length < 1) {
return;
}
if (left < right) {
// 取中间索引
int mid = (right + left) / 2;
// 递归排序左半边
mergeSort5(arr, left, mid, temp);
// 递归排序右半边
mergeSort5(arr, mid + 1, right, temp);
// 合并左右两个有序数组
merge(arr, left, mid, right, temp);
}
}

/**
* 合并两个有序数组
*
* @param arr 原数组
* @param left 左指针
* @param mid 中间索引
* @param right 右指针
* @param temp 临时数组
*/
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 左子数组起始索引
int leftIndex = left;
// 右子数组起始索引
int rightIndex = mid + 1;
// 临时数组索引
int tempIndex = 0;
// 比较左右两部分的元素，将较小的放入temp
while (leftIndex <= mid && rightIndex <= right) {
if (arr[leftIndex] <= arr[rightIndex]) {
temp[tempIndex++] = arr[leftIndex++];
} else {
temp[tempIndex++] = arr[rightIndex++];
}
}
// 将左边剩余元素填充进temp中
while (leftIndex <= mid) {
temp[tempIndex++] = arr[leftIndex++];
}
// 将右边剩余元素填充进temp中
while (rightIndex <= right) {
temp[tempIndex++] = arr[rightIndex++];
}
// 将temp中的元素拷贝到arr中
tempIndex = 0;
while (left <= right) {
arr[left++] = temp[tempIndex++];
}
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr5 = {5, 6, 2, 3, 1, 7, 4};
System.out.println("原数组：" + Arrays.toString(arr5));
int[] tempArr = new int[arr5.length];
mergeSort5(arr5, 0, arr5.length – 1, tempArr);
System.out.println("归并排序后：" + Arrays.toString(arr5));
}

6. 堆排序

• 思路：堆排序(Heap Sort)是一种基于二叉堆数据结构的比较排序算法,排序思路： ①构建堆，将无序数组构建成一个最大堆（或者最小堆） ②排序，每次取出堆顶元素，并调整堆，将堆顶元素放到已排序的末尾，重复n-1次，即可得到一个有序数组。
• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 实现代码：

/**
* 常见的排序算法 之 堆排序(从小到大排列)
* @param arr
*/
public static void heapSort6(int[] arr) {
if (arr == null || arr.length < 1) {
return;
}
// 构建最大堆
buildMaxHeap(arr);
// 逐一交换堆顶元素（最大值）到数组末尾，并调整堆
for (int i = arr.length – 1; i > 0; i—) {
// 将堆顶元素与末尾元素交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// 调整堆，使其重新成为最大堆（堆大小减1）
heapAdjust(arr, 0, i);
System.out.println("堆排序中间过程：" + Arrays.toString(arr));
}
}

/**
* heapAdjust
* @param arr
*/
public static void buildMaxHeap(int[] arr) {
// 从最后一个非叶子节点开始，从下至上，从右至左进行堆化
for (int i = arr.length / 2 – 1; i >= 0; i—) {
// 堆化
heapAdjust(arr, i, arr.length);
}
}

/**
* 调整堆
* @param arr
* @param i
* @param heapSize
*/
public static void heapAdjust(int[] arr, int i, int heapSize) {
// 初始化最大值为当前节点
int largest = i;
// 左子节点
int left = 2 * i + 1;
// 右子节点
int right = 2 * i + 2;
// 如果左子节点大于当前最大节点
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于当前最大节点
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}

// 如果最大节点不是当前节点，交换并继续调整
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapAdjust(arr, largest, heapSize);
}
}

• 测试：

public class SortTest {
public static void main(String[] args) {
int[] arr6 = {5, 6, 2, 3, 1, 7, 4};
System.out.println("原数组：" + Arrays.toString(arr6));
heapSort6(arr6);
System.out.println("堆排序后：" + Arrays.toString(arr6));
}

7. 总结