前言

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

生活中各种地方都需要用到排序，所以学好排序算法是非常重要的。

排序分为内部排序和外部排序。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

这部分主要是内部排序。排序讲解都以升序为例。
————————————————
版权声明：本文为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+1int 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);//对基准点右边进行递归排序}}