一、分治排序法,快速排序法
选择待排数列的首部第一个元素为基准元素，设置两指针，分别指向数列首尾部位置，假设两指针分别设为i和j。每次遍历的过程是这样的，首先遍历指针j所指向的元素，直到j指向的元素值小于基准元素时，停止遍历，将其与指针i所指向的元素进行交换，因为当前指针所指位置就是用于插入较基准元素小的元素，然后再将指针i加一。接着轮到指针i遍历,直到i所指向的元素值大于基准元素时，停止遍历，将其与指针j所指向的元素进行交换，之所以可以交换，是因为指针j所指向的元素刚刚已经交换到前半部分呢，故可以直接选择覆盖就行，这样就将大于基准元素的元素放于后半部分。依此类推，直到指针i与指针相等或者大于时，停止外部循环。最后直接将基准元素直接放置于指针i所指向的位置即可，完成分区操作。
接下来，我们通过示图来展示上述分区算法思路的过程：
public class QuickSort {
public static void sort(int[] arr,int begin,int end) {
//先定义两个参数接收排序起始值和结束值
int a = begin;
int b = end;
//先判断a是否大于b
if (a >= b) {
//没必要排序
return;
}
//基准数,默认设置为第一个值
int x = arr[a];
//循环
while (a < b) {
//从后往前找,找到一个比基准数x小的值,赋给arr[a]
//如果a和b的逻辑正确--a<b ,并且最后一个值arr[b]>x,就一直往下找,直到找到后面的值大于x
while (a < b && arr[b] >= x) {
b--;
}
//跳出循环,两种情况,一是a和b的逻辑不对了,a>=b,这时候排序结束.二是在后面找到了比x小的值
if (a < b) {
//将这时候找到的arr[b]放到最前面arr[a]
arr[a] = arr[b];
//排序的起始位置后移一位
a++;
}
//从前往后找,找到一个比基准数x大的值,放在最后面arr[b]
while (a < b && arr[a] <= x) {
a++;
}
if (a < b) {
arr[b] = arr[a];
//排序的终止位置前移一位
b--;
}
}
//跳出循环 a < b的逻辑不成立了,a==b重合了,此时将x赋值回去arr[a]
arr[a] = x;
//调用递归函数,再细分再排序
sort(arr,begin,a-1);
sort(arr,a+1,end);
}
}
二、冒泡排序(改动版，加入标志位)
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n 次，
就完成了 n 个数据的排序工作。
public void bubbleSort(Integer[] arr, int n) {
if (n <= 1) return; //如果只有一个元素就不用排序了
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) { //此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
// 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
if (arr[j] > arr[j + 1]) { //即这两个相邻的数是逆序的，交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag) break;//没有数据交换，数组已经有序，退出排序
}
}
三、选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
public void selectSort(Integer[] arr){
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
