-
排序算法 - 1、插入排序
- 1.1、简单插入排序
- 1.2、希尔排序
- 2、交换排序
- 2.1、冒泡排序
- 2.2、快速排序
- 3、选择排序
- 3.1、简单选择排序
- 3.2、堆排序
- 4、归并排序
- 附录
好早之前就学了各个排序算法，最近翻出来重新回顾一下，发现大部分的算法还记得，比较细节的算法已经快忘记了，比如说大根堆排序，具体代码如何实现已经快忘光了，只记得算法的大致运行流程了。通过本次复习，加深对各个排序的算法理解。代码注释部分有对各个算法步骤有一定的解释，希望再过一段时间看到这些算法还能有现在所学的理解。加油！靓仔！ 1、插入排序 1.1、简单插入排序
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
InsertSort insertSort = new InsertSort();
insertSort.print(arr);
insertSort.sort(arr);
insertSort.print(arr);
}
public void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j > 0) {
if (arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
}
arr[j] = temp;
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
1.2、希尔排序
public class ShellSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
ShellSort shellSort = new ShellSort();
shellSort.print(arr);
shellSort.sort(arr);
shellSort.print(arr);
}
public void sort(int[] arr) {
for (int gap = 4; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
}
}
public void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
2、交换排序
2.1、冒泡排序
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.print(arr);
bubbleSort.sort(arr);
bubbleSort.print(arr);
}
public void sort(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
2.2、快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
QuickSort quickSort = new QuickSort();
quickSort.print(arr);
quickSort.sort(arr, 0, arr.length - 1);
quickSort.print(arr);
}
public void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int q = partition(arr, left, right);
sort(arr, left, q - 1);
sort(arr, q + 1, right);
}
int partition(int[] arr, int left, int right) {
int temp = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] <= temp) {
i++;
}
while (i <= j && arr[j] > temp) {
j--;
}
if (i >= j) {
break;
}
swap(arr, i, j);
}
swap(arr,left,j);
return j;
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
3、选择排序
3.1、简单选择排序
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
SelectSort selectSort = new SelectSort();
selectSort.sort(arr);
selectSort.printArr(arr);
}
public void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minPosition = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minPosition] > arr[j]) {
minPosition = j;
}
}
swap(arr, i, minPosition);
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void printArr(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
3.2、堆排序
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
HeapSort heapSort = new HeapSort();
heapSort.printArr(arr);
heapSort.sort(arr);
heapSort.printArr(arr);
}
public void sort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjust(arr, i, arr.length);
}
for (int i = arr.length - 1; i >= 0; i--) {
swap(arr, 0, i);
adjust(arr, 0, i);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void adjust(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) { // 比较左右子节点的大小，选择一个大的子节点继续进行下去
k++;
}
if (temp > arr[k]) { // 如果根节点temp已经最大了，就break退出
break;
} else {
arr[i] = arr[k]; // 将大的值赋值给i
i = k; // 以k作为根节点
}
}
arr[i] = temp;
}
public void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
4、归并排序
归并排序的核心思想是采用分治法思想化整为零，逐个击破，因此时间复杂度要低于O(n^2)，其时间复杂度是O(nlogn)。具体代码实现暂时还没有放过来。后续复习再把代码放过来吧
附录上面的算法代码作者已经将其打包到gitee上了，需要的好友可以自取source_code。
最后，推荐一个算法网站，此网站囊括了各个排序算法的动态分析图，这是一个英文网站。
