直接插入排序
直接插入排序是一种简单排序算法，基本思想是将一个记录插入已经排好序的有序表中，从而得到一个新的，记录数+1的有序表。
核心思想
1.将数组分为已排序和未排序两部分，起初已排序部分只有一个元素
2.从未排序部分取出一个元素，已排序部分从后向前逐一比较
3.如果已排序元素大于新元素，则将已排序元素向后移动一位
4.重复步骤3，直到遇到已排序元素小于等于新元素
5.插入该位置
6.重复2-5，直到未排序部分全部插入已排序部分
代码实现
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
int temp,j;
//从第一个元素之后一个元素开始插入
for (int i = 1; i < array.length; i++) {
//是否需要排序
if (array[i] < array[i-1]){
//需要插入排序
temp = array[i];
//逐一比较，直到到达末尾或找到已排序元素小于插入值
for (j = i - 1; j >= 0 && array[j] > temp; j--) {
//该数字向后移动一位
array[j + 1] = array[j];
}
array[j+1] = temp;
}
}
print(array);
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
时间：O(n^2) 空间：O(1)
希尔排序
希尔排序是直接插入排序的一种改进版本，通过引入“增量”的概念来提高排序效率。希尔排序的基本思想是将待排序的数组按照一定的增量分成多个子序列，然后对每个子序列进行直接插入排序。随着增量的逐渐减小，整个数组会越来越接近有序，最后当增量减至1时，整个数组就变成了一个子序列，再进行一次直接插入排序，完成整个排序过程。
核心思想
1.选定一个初始增量，如当前数组长度/2，也就是2个元素一组
2.按照每组元素个数k，对整个数组做k趟排序（每趟都对每个分组做一次插入排序）
代码实现
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
int j,temp;
//gap为分组增量
for (int gap = array.length/2; gap > 0; gap/=2) {
for (int i = gap; i < array.length; i++) {
//不断进行分组插入，i++每组进行下一个元素插入
temp = array[i];
//比较并插入
for (j = i; j >= gap && array[j - gap] > temp ; j-=gap) {
array[j] = array[j - gap];
}
//插入元素
array[j] = temp;
}
}
print(array);
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
最坏情况下的时间复杂度为 ( O(n^2) )，但对于中等大小的序列，它的时间复杂度通常优于 ( O(n^2) )
选择排序
选择排序（Selection Sort）是一种简单且直观的排序算法。它的工作原理是不断地选择剩余元素中的最小者。
核心思想
1.从数组中当前位置开始，选择一个最小元素
2.将最小元素与当前数组位置元素替换
3.数组当前位置后移一格，重复步骤1.2
代码实现
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
int temp;
int index;
//开始选择排序
for (int i = 0; i < array.length; i++) {
index = i;
//在当前数组中选择最小元素
for (int j = i+1; j <array.length; j++) {
if (array[j] < array[index]){
index = j;
}
}
//交换
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
print(array);
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
时间：O(n^2) 空间：O(1)
堆排序
堆排序（Heap Sort）是一种基于堆结构的排序算法。堆是一个特殊的完全二叉树，其中每个父节点的值都大于或等于其子节点（最大堆）或小于或等于其子节点（最小堆）。堆排序算法包括两个主要步骤：构建堆和排序。
堆排序的步骤如下：
- 构建最大堆：从最后一个非叶子节点开始，对每个父节点执行下沉操作，确保所有的父节点都大于其子节点。
- 排序：将最大堆的根节点（数组的第一个元素）与最后一个元素交换，然后减小堆的大小并重新构建最大堆。重复这个过程直到堆的大小为1。
堆排序的时间复杂度为 ( O(n log n) )，空间复杂度为 ( O(1) )，是一种不稳定的排序算法。
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is an index in arr[] and n is size of heap
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left child
int r = 2 * i + 2; // right child
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to print array of size n
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
堆排序是一种高效的排序算法，特别适合处理大数据集。它的时间复杂度为 ( O(n log n) )，并且不需要额外的存储空间。
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历要排序的数列，比较每对相邻元素，并在顺序错误时交换它们。这个过程一直重复，直到没有需要交换的相邻元素，也就是数列已经排序完成。冒泡排序的名字来源于较小的元素会像气泡一样逐渐“浮”到数列的顶端。
核心思想
1.每次都从头部开始比较，前后元素两两比较，如果前面的元素大于后面的元素，则交换两个元素
2.对于每个相邻元素都做次工作，则最后一个元素将是最大的元素
3.重复1.2步骤，除了最后一个，因此该趟次数比上一趟减少一次
4.重复以上步骤直到没有一对数字需要比较
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
int temp;
//冒泡排序
for (int i = 0; i < array.length - 1; i++) {
//不断将较小的替换到前面，最后一个元素将是本趟最大元素
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j+1]){
temp =array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
print(array);
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
时间：O(n^2) 空间O(1)
快速排序
快速排序（Quick Sort）是一种高效的排序算法，它使用分治法的策略，通过一趟排序将待排序的记录分隔成独立的两部分，其中一部分的所有记录都比另一部分的记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
核心思想
1.选取一个元素（这里选择第一个）作为基准值
2.从右指针记录位置开始，不停向右寻找一个比基准值小的数字，和基准值交换，并更新右指针位置
3.从左指针记录位置开始，不停向左寻找一个比基准值大的数字，和基准值交换，并更新左指针位置
4.重复2，3直到左指针大于右指针，此时基准左边的数应当都小于基准值，基准右边的数应当都大于基准值，对基准值左边部分和右边部分都重复以上步骤，直到整个数组有序
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
quickSort(array,0,array.length-1);
print(array);
}
private static void quickSort(int[] array, int low, int high) {
if (low < high){
//p为基准索引
//i,j作为左右遍历双指针使用
int p = low,i = low,j = high;
int temp;//用于交换
//开始一趟快速排序
while (i <= j){
//先从右边开始找比基准小的进行交换
while (i <= j){
if (array[j] < array[p]){
temp = array[p];
array[p] = array[j];
array[j] = temp;
p = j;//基准值位置更新
j--;
break;
}
j--;
}
//再从左边找比基准大的进行交换
while (i <= j){
if (array[i] > array[p]){
temp = array[p];
array[p] = array[i];
array[i] = temp;
p = i;//基准值位置更新
i++;
break;
}
i++;
}
}
//对基准左边部分做快速排序
quickSort(array,low,p-1);
//对基准右边部分做快速排序
quickSort(array,p+1,high);
}
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
快速排序的平均时间复杂度为 ( O(n log n) )，但最坏情况下可以退化到 ( O(n^2) )。它不是一个稳定的排序算法
归并排序
归并排序（Merge Sort）是一种高效且稳定的排序算法，它基于分治法的原理。归并排序将数组分成两半，递归地对它们进行归并排序，然后将结果合并成一个有序数组。
核心思想
1.递归式的对原数组进行二分（这里取中点）
2.不断二分，直到数组只有一个元素时，该数组就是有序的，返回
3.将二分的左边部分和右边部分进行合并，左右两部分是单独有序的，创建一个新的数组，通过双指针不断将两个部分中相对较小的数放入新数组，最后合并两个旧数组，将新数组的值赋值回原数组对应部分。
4.回归，重复3，直到原数组有序
public class Main {
public static void main(String[] args) {
int[] array = {9,3,5,2,1,6,7,3,6,7,8,0,2,4};
//归并排序数组
sort(array,0,array.length-1);
print(array);
}
private static void sort(int[] array,int low,int high) {
if (low == high)return;
//切割点取中点，将数组切割为两个数组
int mid = low + (high - low) / 2;
//排序左边
sort(array,low,mid);
//排序右边
sort(array,mid+1,high);
//合并左右两个有序列表
merge(array,low,mid,high);
}
private static void merge(int[] array, int low, int mid, int high) {
//新数组，用于存储合并结果
int[] temp = new int[high - low + 1];
int i = low,j = mid+1,k = 0;
//需要比较，将较小值不断放入新数组
while (i <= mid && j <= high){
if (array[i] < array[j]){
temp[k++] = array[i++];
}else {
temp[k++] = array[j++];
}
}
//如果有剩余部分则继续放入新数组
while (i <= mid){
temp[k++] = array[i++];
}
while (j <= high){
temp[k++] = array[j++];
}
//将合并后的新数组赋值给原数组这两个数组原来的位置
for (k = 0; k < temp.length; k++) {
array[low + k] = temp[k];
}
}
private static void print(int[] array) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i : array) {
sb.append(i);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
System.out.println(sb.toString());
}
}
归并排序的时间复杂度为 ( O(n log n) )，空间复杂度为 ( O(n) )。由于归并排序在合并过程中不会改变相同元素之间的相对顺序，因此它是一种稳定的排序算法。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
