目录
前言
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
生活中各种地方都需要用到排序，所以学好排序算法是非常重要的。
排序分为 内部排序 和 外部排序。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
这部分主要是内部排序。排序讲解都以升序为例。
————————————————
版权声明：本文为CSDN博主「风继续吹TT」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Edward_Asia/article/details/121419975
常见的四种排序算法：
1. 冒泡排序
2. 选择排序
3.插入排序
4.快速排序
常见的排序算法实现：
1. 冒泡排序
思路分析：
1.两两相邻元素比较，大的元素往后移，直到让最大的元素在最后面
2.当有n个元素时，外循环会进行（n-1）次排序，因为最后剩下一个数，不需要比较
3.当进行第i趟排序时，内循环会进行n-i次比较
代码实现：
//冒泡排序
public void BubbleSort( int[] arr)
{
//整体思路：通过每一次循环的比较找到最大值
int n=arr.length;
//外层排序n-1次
for(int i=0;i<n-1;i++)
{
//内层比较n-i-1次
for(int j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])//交换相邻的两个数组，将大的往后排
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}2.选择排序
思路分析：
1.首先，找到数组中最大（小）的那个元素;
2.其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）;
3.再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。总结：这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最大（小）者
代码实现：
//选择排序
public void SelectSort ( int[] arr)
{
int n=arr.length;
//整体思路；内循环找到最小值的下标，与第一个数交换，重复找小，交换
for(int i=0;i<n-1;i++)
{
int minIndex=i;
for(int j=i+1;j<n;j++)
{
if(arr[j]<arr[minIndex])//如果此时minIndex索引处的值不是最小的，交换
{
minIndex=j;
}
}
//交换arr[i]和arr[minIndex]
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}3.插入排序
思路分析：
1.对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2.为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向右移动一位。
3.插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组
4.进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多
代码实现：
//插入排序
public void InsertSort(int[] arr)
{
int n=arr.length;
//整体思路：从认为第一个元素有序开始，依次将后面的元素插入到这个有序序列中来，直到整个序列有序为止
for(int i=1;i<n;i++)//从第二个元素开始遍历
{
int key = arr[i];//当前插入的元素
int j = i - 1;
while (j >= 0 && arr[j] > key)//将key插入到前面有序数组的合适位置
{
arr[j + 1] = arr[j];//把arr[j]后移一位
j--;//j减1继续比较，直到找到合适的位置
}
arr[j + 1] = key;
}
}4.快速排序
思路分析：
1.将待排序的序列找一个基准值（通常选最两边）
2.采用递归的思想，将小于基准值的放在他前面，大于基准值的在他后面
代码实现：
//快速排序
public static void QuickSort(int[] arr)//对外提供的排序方法，方便用户调用
{
QuickSort(arr,0,arr.length-1);
}
//用递归排序对数组进行分区，小于基准点的在左边，大于基准点的在右边
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];//选择最右边为基准点
int i = left-1;//初始一个小于元素边界的变量
for(int j=left;j<right;j++)
{
if(arr[j]<=pivot)//如果当前元素小于基准点
{
i++;
//交换arr[i]和arr[j]，将小于基准点的元素放在前面
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//将基准点放在正确的位置上，既i+1
int temp = arr[i+1];
arr[i+1] = arr[right];
arr[right] = temp;
return i+1;//返回基准点的最终位置aaaaaalaakka
}
//-------------------------------------------------------------------
private static void QuickSort(int[] arr,int left,int right)//核心的递归排序方法，left表示当前排序的左边界，right表示用边界
{
if(left<right)
{
int pivot=Partition(arr,left,right);
QuickSort(arr,left,pivot-1);//对基准点左边进行递归排序
QuickSort(arr,pivot+1,right);//对基准点右边进行递归排序
}
}