先说一下快速排序的主要思路：每一轮排序我们会把数组中的一个数作为基准数，一般会把数组最左边或者最右边的数当作基准数，这里我们把最左边的数当作基准数，基准数确定后，我们会从两边开始进行检索，先从数组的右边检索，检索比基准数小的数，如果检索到了就先停下来，再从左边开始检索比基准数大的数，检索到了也停下来，此时当两边都停下来了，就把这两个位置的数进行交换，交换完成继续检索（当然是先从右边开始，以此类推继续检索），检索时，当左右两边检索到同一位置时，意味着这一轮的排序结束，将此位置的数与基准数交换，此时我们发现数组会有什么特点呢？
以此类推，我们就可以把一组数组的数排序完成。
特点：基准数右边的都是比基准数大的数，基准数左边的都是比基准数小的数。
下面我们通过实例来帮助我们理解快速排序：
这是一个数组{6，1，2，7，9，3，4，5，10，8}，我们使用快速排序的方法将他们排好序。
得到一个排序成功的数组
程序代码public class Demo {
public static void main(String[] args) {
int[] arr = {6,1,2,7,9,3,4,5,10,8};
quickSort(arr,0,arr.length -1);
System.out.println();
}
private static void quickSort(int[] arr,int left,int right){
//left 左指针
//right 右指针
//如果数组是空的或者数组长度不大于1或者左指针大于右指针，重叠了
//if条件如果满足直接返回，程序结束
if(arr == null || arr.length >= 1 || left >= right){
return;
}
//定义一个key作为中间值,将数组的第一个值赋给key
int key = arr[left];
//移动指针的操作
while(left != right){
//先移动右指针
//当右指针大于key的时候和左指针大于右指针的时候
while (arr[right] >= key && left < right){
//右指针左移，做--运算
--right;
}
//移动左指针
while (arr[left] <= key && left < right){
//左指针右移，做++运算
++left;
}
//交换两指针中的值
if(left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//交换key值和重叠值
arr[left] = arr[left];
arr[left] = key;
//再完成两边递归
quickSort(arr,left,left-1);
quickSort(arr,left +1,right);
}
}
冒泡排序
思路
1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3）针对所有的元素重复以上的步骤，除了最后一个；
4）重复步骤1~3，直到排序完成
程序代码public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
public static void bubbleSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
// 外层循环控制比较轮数i
for (int i = 0; i < length; i++) {
// 内层循环控制每一轮比较次数，每进行一轮排序都会找出一个较大值
// (array.length - 1)防止索引越界，(array.length - 1 - i)减少比较次数
for (int j = 0; j < length - 1 - i; j++) {
// 前面的数大于后面的数就进行交换
if (array[j] > array[j + 1]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
选择排序
思路
1）初始状态：无序区为R[1…n]，有序区为空；
2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3）n-1趟结束，数组有序化了
程序public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
selectionSort(array);
System.out.println(Arrays.toString(array));
}
public static void selectionSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
for (int i = 0; i < length - 1; i++) {
// 保存最小数的索引
int minIndex = i;
for (int j = i + 1; j < length; j++) {
// 找到最小的数
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 交换元素位置
if (i != minIndex) {
swap(array, minIndex, i);
}
}
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
插入排序
思路
1）从第一个元素开始，该元素可以认为已经被排序；
2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5）将新元素插入到该位置后；
6）重复步骤2~5。
程序代码public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
insertionSort(array);
System.out.println(Arrays.toString(array));
}
public static void insertionSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
// 要插入的数
int insertNum;
for (int i = 1; i < length; i++) {
insertNum = array[i];
// 已经排序好的元素个数
int j = i - 1;
while (j >= 0 && array[j] > insertNum) {
// 从后到前循环，将大于insertNum的数向后移动一格
array[j + 1] = array[j];
j--;
}
// 将需要插入的数放在要插入的位置
array[j + 1] = insertNum;
}
}
