定义：从待排序的数据中，按指定的规则选出某一个元素，再依规定交换位置后达到排序的目的。
核心思想：从全部序列中选取最小的，与第0个元素交换，然后从第1个元素往后找出最小的，与第一个元素交换。再从第2个元素往后选取最小的，与第二个元素交换，直到最后一个元素。
代码：
//选择排序
//核心思想：不断遍历数组的每个位置，并且为每个位置选择当前数组中最小的元素填入。
//思路分析：遍历数组的每个位置需要一层for循环，为每个位置遍历选择最小值也需要一层for循环。
public static void sort1(int [] arr){
//第一层for循环，遍历数组中的每个位置，最后一个位置无需遍历，因为最后一个位置只剩下最后一个元素，不需要寻找最小值，直接使用即可
for(int i=0;i<arr.length-1;i++){
//第二层for循环，遍历数组中位置i之后的剩余元素，找到最小值，与位置i上的元素值交换
int min=arr[i]; //定义最小值
int min_index=i; //定义最小值对应的位置索引
for(int j=i+1;j<arr.length;j++){
if(arr[j]<min){
min=arr[j];
min_index=j;
}
}
//内层for循环结束后，即找到了位置i应该填入的最小值
//将最小值与位置i上的值交换
arr[min_index]=arr[i];
arr[i]=min;
}
}定义：冒泡排序通过对待排序序列从前往后，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。
核心思想：冒泡排序总共进行n-1趟冒泡，每趟冒泡两两比较元素的大小，若前面的元素大于后面的元素，则交换两个元素，这样可将整个待排序序列中最大的元素冒泡到最后，随后缩小待排序序列的长度，进行第二趟冒泡排序，直到第n-1趟冒泡排序结束，即可得到最终的排序序列。
改进：排序过程中，各个元素不断接近自己的位置，如果一趟比较下来，没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。
代码：
//冒泡排序
//核心思想：对数组进行n-1趟排序，每趟排序两两比较元素数值大小，每趟将最大值冒泡到数组的末尾。总共进行n-1趟排序，每一趟的排序次数逐渐减少。
//思路分析：对数组进行n-1趟排序，需要使用一层for循环；每趟遍历内部，需要两两比较元素值的大小，需要使用内部for循环，每趟的排序规模逐渐减少，即每趟都减少排序规模
//示例：3,9，-1,10，-2
public static void sort2(int [] arr){
//第一层for循环表示排序的趟数，总共进行n-1趟
for(int i=0;i<arr.length-1;i++){
//第二层for循环表示每趟排序时，依次比较前后两个元素的大小关系，若满足交换条件，则交换两个元素的位置
//注意：每趟排序都不断缩小排序规模，即末尾已经确定的元素不需要参与排序（第一趟后可以确定一个值，第二趟后可以确定两个值。。。）
for(int j=0;j<arr.length-1-i;j++){
//若前面的元素比后面的元素大，则交换两个元素的位置
if(arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}核心思想：归并排序的思想是利用二分的特性，将序列分为两个子序列进行排序，然后将排序后的两个子序列归并（合并），当序列的长度为2时，它的两个子序列长度为1，即视为有序，可直接合并，即达到归并排序的最小子状态。注意：两个子序列进行合并的时候类似于两个有序链表的合并。
代码：
//归并排序
//核心思想：归并排序又叫2-路归并排序，其核心思想是先划分在合并。
// 划分阶段：使用递归完成，将待排序的数组按照2分法的原则划分，指导划分为单个元素位置（即8个元素的待排序数组，
// 第一次划分为4和4的待排序数组，第二次划分为2，2，2，2的待排序数组，第三次划分为1,1,1,1,1,1,1,1的待排序数组）。
// 合并阶段：将排好序的两个子数组合并为一个新的数组（类似于合并两个有序链表），在该阶段，需要借助一个辅助数组，用于存放两个有序子序列的排序结果，
// 最后将辅助数组中的排序结果拷贝到原数组中
//思路分析：整体思路采用递归思想，即每次划分后都伴随着一次合并，递归结束的条件是划分的子序列为单个元素，即子序列的首位指针相等。合并阶段类似于两个有序列表的合并。
public static void sort6(int [] arr,int start,int end ){
int [] temp=new int [arr.length];
if(start>=end){ //递归结束的条件
return;
}else{
sort6(arr, start, (start+end)/2); //对左边序列使用递归，完成划分
sort6(arr, (start+end)/2+1, end); //对右边序列使用递归，完成划分
merge(arr,temp,start,end); //将左右两边的序列合并，得到完整的有序序列
}
}
//合并（类似于两个有序链表的合并）
private static void merge(int[] arr,int [] temp, int start, int end) {
int mid=(start+end)/2;
int i=start;
int j=mid+1;
int k=0;
//两个有序有序列均非空
while(i<=mid && j<=end){
if(arr[i]<arr[j]){
temp[k]=arr[i];
i++;
k++;
}else{
temp[k]=arr[j];
j++;
k++;
}
}
//两个子序列其中一个非空，左边子序列还有剩余元素
while(i<=mid){
temp[k]=arr[i];
i++;
k++;
}
//两个子序列其中一个非空，右边子序列还有剩余元素
while(j<=end){
temp[k]=arr[j];
j++;
k++;
}
//将临时数组temp中的元素导入arr中的相应位置
//arr中元素的起止位置分别为start和end，temp中元素的起止位置分别为0和k-1
int temp_index=start;
for(int m=0;m<k;m++){
arr[temp_index]=temp[m];
temp_index++;
}
}定义：把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中，每次从无序表中取出一个第一个元素，把它与有序表中的元素进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
核心思想：插入排序的思想类似于扑克牌的排序，每次从未排序序列的第一个元素，插入到已排序序列汇总的合适位置。假设初始的有序序列为第1个元素（数组中的下标为0），后续的序列为待排序序列。每次选取待排序序列的第一个元素，与前面有序序列进行比较，找到合适的位置并插入（从后往前比较，同时挪动位置）。
问题：当需要插入的数是比较小的数时，后移的次数明显增加，对效率有影响。
代码：
//插入排序
//核心思想：插入排序主要强调插入，即将整个数组分为两个部分，已排序部分和未排序部分，依次将未排序部分的值插入到已排序部分的正确位置
//思路分析：整个数组分为已排序部分和未排序部分，初始状态为：第一个元素为已排序部分，剩余部分为未排序部分。通过一层for循环依次遍历未排序部分的每个元素，
// 并不断扩大已排序部分的规模。其中对于 每个未排序部分的元素需要依次遍历已排序部分，找到合适的位置插入
public static void sort3(int [] arr){
//排序的初始状态为：数组中的第一个元素为已排序部分，剩余所有元素构成未排序部分
//第一层for循环，依次遍历未排序部分的每个元素，未排序部分的数组下标范围：1到arr.length-1
for(int i=1;i<arr.length;i++){
int temp=arr[i]; //保存待插入元素的数值
int j=i-1;
//从后往前依次遍历已排序部分的每个元素，最终找到合适的插入位置（此处采用移动的方法，直到找到合适的位置才做插入）
while(j>=0){
//判断是否满足元素移动条件，若满足移动条件，则将前一个元素移动到后一个元素的位置
if(arr[j]>temp){
arr[j+1]=arr[j];
j--;
}else{//若不满足移动条件，则说明找到了合适的位置，通过break语句跳出循环
break;
}
}
//内层while循环结束后，表示找到了合适的插入位置，此时将待插入的元素插入合适的位置
arr[j+1]=temp;
}
}定义：希尔排序是把记录按照下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量较少至1时，整个文件恰被分成一组，算法便终止。
核心思想：希尔排序时对插入排序的一种改进。插入排序一个比较耗时的地方在于需要将元素反复移动，因为它是以1位增量进行比较的元素的后移可能会进行很多次。一个长度为n的序列，以1位增量就是一个序列，以2位增量就形成两个子序列，以i为增量就形成i个子序列。希尔排序的思想就是，先以一个较大的增量，将序列分为几个子序列，将这几个子序列分别排序后，再缩小增量进行同样的操作，直到增量为1时，序列已经基本有序。
代码：
//希尔排序
//核心思想：希尔排序是对直接插入排序的改进，采用分轮次使用插入排序的方法，第一轮分为数组长度除以2个组，每个组使用直接插入排序；第二个轮次分为上个分组除以2个组
// 直到最后的分组数目为1。
//思路分析：首先需要一层循环，依次进行多个轮次的循环；在每个轮次内，需要对每个分组内的元素进行直接插入排序，由于不同轮次内， 每个分组内元素个数不同，
// 因此采用while循环判断。
public static void sort4(int [] arr){
//第一层for循环，表示不同的轮次，轮次的划分使用数组长度除以2，继续除以2.......直到最后等于1
for(int gap=arr.length/2;gap>0;gap=gap/2){
//第二层for循环，表示每个轮次内，对每个分组的元素使用直接插入排序
for(int i=gap;i<arr.length;i++){
//内部使用插入排序
int temp=arr[i];
int j=i;
//由于不同轮次内，每个分组的元素个数不同，且元素之间的步长不同，所以使用while循环，依次找寻待插入元素的合适位置（与直接插入排序思想一致）
while(j-gap>=0){
//判断是否满足元素移动条件，若满足移动条件，则将前一个元素移动到后一个元素的位置
if(arr[j-gap]>temp){
arr[j]=arr[j-gap];
j=j-gap;
}else{//若不满足移动条件，则说明找到了合适的位置，通过break语句跳出循环
break;
}
}
//内层while循环结束后，表示找到了合适的插入位置，此时将待插入的元素插入合适的位置
arr[j]=temp;
}
}
}定义：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对两部分数据进行分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据编程有序序列。
核心思想：快速排序的思想是选取第一个数字为基准值，并通过待排序序列的左右两个索引，通过一次遍历将小于基准值的元素放在它的左侧，将大于它的索引放到它的右侧，然后对它的左右两个子序列分别递归执行同样的操作。
代码：
//快速排序
//核心思想：快速排序首先选取一个基准值，并从数组的左右两端分别计较，从左边找比基准值大的元素，从后边找比基准值小的元素，并交换这两个元素的位置，
// 使得基准值左边元素都比它小，基准值右边元素都比它大。最后使用递归的思想，对基准值左右两边的部分分别使用快速排序。
//思路分析：快速排序采用递归的思想，首先需要基准值（一般选取第一个元素作为基准值），数组左右两边的索引。从左右两边分别寻找待交换元素的位置
// （从左边找比基准值大的元素，从右边找比基准值小的元素），并交换这两个元素，直到左右两边的索引值相等，即左边都是比基准值小的元素，右边都是比基准值大的元素
// 此时将基准值与i=j对应的位置互换，并分别对基准值左右两边的子序列递归使用快速排序
public static void sort5(int [] arr,int start,int end){
int i=start;
int j=end;
int base=arr[start];
//递归结束条件！！！
if(start>=end){
return;
}
while(j>i){
//从右边开始寻找比基准值小的元素
while(j>i && arr[j]>=base){
j--;
}
//从左边开始寻找比基准值大的元素
while(j>i && arr[i]<=base){
i++;
}
//判断左右两边是否找到了需要交换的元素，如果找到了，则交换左右两边的元素
if(j>i){
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
//基准值base放到i=j的位置
arr[start]=arr[i];
arr[i]=base;
//分别对基准值左右两边的数组进行递归快速排序
sort5(arr, start, i-1);
sort5(arr, i+1, end);
}核心思想：基数排序是典型的空间换时间的排序方法，在正数范围内，将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始，一次进行一次排序。这样从最低位（个位）排序一直到最高位排序完成以后，数列就变成一个有序序列。
代码：
//基数排序（不处理负数）
//核心思想：基数排序是按照基数进行的排序，将证书按照位数切割成不同的数字，然后按照每个位数进行比较，首先根据个位数字的大小，将待排序的所有数字加入到相应的桶中，
// 随后将桶中的数字按照从前到后的顺序依次加入到原数组中，接下来按照百位数字的大小重复上述操作，循环的轮数取决于待排序序列中最大值的位数。
//思路分析：基数排序时，首先需要确定待排序序列中的最大值，并确定其位数。最大值的位数决定基数排序的轮次。在每个轮次内，需要将数组中待排序的数字加入到相应的桶中，
// 随后按照一定的顺序将各个桶中的数字重新加入到原数组中。待所有轮次完成后，最终数组即是排好序的数组。
// 基数排序首先需要定义0到9十个桶，用来存放待排序的数字，所以需要构建一个二维数组。
public static void sort7(int [] arr){
//1.首先确定最大值
int max=arr[0];
for(int i=0;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
//2.确定最大值的位数，即后续基数排序的轮次
int k=(max+"").length();
//定义二维数组，表示10个桶及其容量
int [][] bucket=new int [10][arr.length];
//定义一维数组，用来存放10个桶中数据大小
int [] bucketElementCounts=new int [10];
//3.基数排序
//第一层for循环表示基数排序循环的轮次
for(int i=0;i<k;i++){
//3.1 第二层for循环依次将待排序数组中的元素放入相应的桶中
for(int j=0;j<arr.length;j++){
//确定待排序元素要放入的桶的下标索引
int index=(int) (arr[j]/Math.pow(10, i)%10); //依次取个位，十位，百位.....
//将待排序的元素放入相应的桶中
bucket[index][bucketElementCounts[index]]=arr[j];
bucketElementCounts[index]++;
}
//3.2 依次将桶中的数据放回到原数组中
int temp_index=0;
//依次遍历各个桶
for(int m=0;m<bucketElementCounts.length;m++){
//判断每个桶中是否有数据，如果有数据，将数据添加到原数组中
if(bucketElementCounts[m]>0){
for(int n=0;n<bucketElementCounts[m];n++){
arr[temp_index]=bucket[m][n];
temp_index++;
}
}
//将bucketElementCounts数组中纪录桶中数据量的值置为0，以供下次基数排序使用
bucketElementCounts[m]=0;
}
}
}核心思想：堆排序时利用二叉树的思想，所谓的堆就是一棵完全二叉树。完全二叉树可以使用一块连续的内存空间（数组）来存储，而不需要指针操作。堆排序分为两个流程：首先是构建大顶堆，然后是从大顶堆中获取按逆序提取元素。注意：大顶堆时一课完全二叉树，每一个结点的值都大于等于其子结点的值。在数组中存储完全二叉树，第i个节点的父结点序号为（i-1）/2，左子结点序号为2*i+1，右子结点序号为2*i+2。构建大顶堆的过程即是从后向前遍历所有非叶子结点，若它小于左右子结点，则与左右子结点中最大的交换，然后递归地对原最大结点进行同样的操作。
构建大顶堆：
从大顶堆逆序提取元素：
代码：
//堆排序
//核心思想：堆排序采用堆的数据结构进行排序，堆满足两个条件：堆是一棵完全二叉树，父结点的值大于等于左右结点的值。在进行堆排序时，首先将待排序序列构成大顶堆，然后将
// 大顶堆的堆顶元素和末尾元素进行交换，并缩小待排序序列的长度。随后按照上述的情况，进行第二次堆排序，直到最后的排序序列长度为1
//思路分析：首先需要一层循环，表示待排序序列的长度逐渐缩小。在该循环内，需要将目前待排序序列构成大顶堆，并将最后的元素和堆顶的元素进行交换，最后最小待排序序列的长度。
public static void sort8(int [] arr){
//第一层for循环，逐渐缩小待排序序列的长度，直到最后的待排序序列的长度为1
for(int i=arr.length;i>=1;i--){
//在当前待排序序列中，将待排序序列化为大顶堆，随后将对顶元素与最后一个元素进行交换，并缩小待排序序列的长度
//第二层for循环，表示从最后一个非叶子结点开始，到第一个非叶子结点结束，将待排序序列化为大顶堆
//最后一个非叶子结点的索引：（当前待排序序列的长度-1）/2
for(int j=(i-1)/2;j>=0;j--){
heapify(arr, j, i); //其中i表示当前待排序序列的长度，该长度随着第一层for循环逐渐缩小；j表示当前需要进行大顶堆化的结点，该值随着第二层for循环逐渐减小，直到第一个结点结束
}
//上述所有非叶子结点遍历完成，即完成当前待排序序列化为大顶堆的操作，接下来交换最后一个元素和对顶元素
int temp=arr[0];
arr[0]=arr[i-1]; //当前待排序序列的长度为i，所以当前待排序序列的最后一个元素下表索引为i-1
arr[i-1]=temp;
}
}
//将以当前结点为根节点的子树化为大顶堆
//arr数组表示当前待排序序列，i表示当前结点，length表示当前待排序序列的长度
public static void heapify(int [] arr,int i,int length){
//由于本函数使用了递归，所以需要加入递归结束的条件
if(i>=length){ //由于当前结点不断扩展到其子结点，所以递归结束的条件是当前结点的索引小标大于当前待排序序列的长度
return;
}
int c1=2*i+1;
int c2=2*i+2;
int max_index=i;
//在当前结点的左右子结点中，寻找最大值
if(c1<length && arr[max_index]<arr[c1]){
max_index=c1;
}
if(c2<length && arr[max_index]<arr[c2]){
max_index=c2;
}
//判断当前结点的值是否是左右子结点中的最大值，若不是才满足交换的条件
if(max_index!=i){
//交换当前结点和拥有最大值的子结点
int temp=arr[i];
arr[i]=arr[max_index];
arr[max_index]=temp;
//交换完成后，对该交换的子结点递归，继续将其子树化为大顶堆
heapify(arr, max_index, length);
}
}
冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
稳定算法：冒泡排序，插入排序，归并排序，基数排序
不稳定算法：选择排序，希尔排序，快速排序，堆排序
