冒泡排序:从0索引开始向后比较,比后一位数大就交换位置,每次循环结束找出一个大的数放到最后。
//冒泡排序
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
//内循环是用于排序
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
//比下一个数大就交换位置
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
快速排序:主要思想——假定一个基准数,一般设定0索引处,然后将小的数放到左边,大的放到右边。然后将两边的数组递归。
//快速排序
private static void quickSort(int[] arr, int low, int high) {
//跳出递归条件
if (low >= high) {
return;
}
//先记录开始的索引
int left = low;
int right = high;
//基准数
int temp = arr[low];
while (left < right) {
//升序排列先从右边开始
while (left < right && arr[right] >= temp) {
//如果右边的数比基准数大就指针左移,直到找到小的数
right--;
}
while (left < right && arr[left] <= temp) {
//如果左边的数比基准数小就指针右移,直到找到大的数
left++;
}
//交换找到的两个数
int tempT = arr[left];
arr[left] = arr[right];
arr[right] = tempT;
}
//循环结束将指针停下的位置跟基准数原位置交换
arr[low] = arr[left];
arr[left] = temp;
//再将两边的数递归排序
quickSort(arr, low, left);
quickSort(arr, left + 1, high);
}
插入排序:主要思想——将待插入数放入已排好序的数组中,找到合适插入位置就停下插入。
一般把1索引处当成插入数,0索引当作已排好序得数组
//插入排序
private static void insertSort(int[] arr) {
//必须是长度大于1.
/*for (int i = 1; i < arr.length; i++) {
//待插入数
int temp=arr[i];
while (temp < arr[i - 1]) {
//待插入的数比原来的数小就将原来的数往后移动1位
arr[i] = arr[i - 1];
if (i-- == 1) {
break;
}
}
arr[i]=temp;
}
*/
for (int i = 0; i < arr.length - 1; i++) {
//待插入数
int temp = arr[i + 1];
while (arr[i] > temp) {
arr[i + 1] = arr[i];
if (i-- == 0) {
break;
}
}
//循环结束将待插入数放到指针停下位置
//这里循环跳出时,不满足的数是arr[i],应在i+1处插入
arr[i + 1] = temp;
}
}
归并排序:主要思想——将数组不断拆分,然后分别排序,两两合并。
//归并排序
private static void mergeSort(int[] arr, int low, int high) {
//跳出递归条件
if (low == high) {
return;
}
//找出中间数,分治两个数组
int mid = (high + low) / 2;//这里是+法运算
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
//将有序的两个数组合并
merge(arr, low, mid, high);
}
//将有序的两个数组合并
private static void merge(int[] arr, int low, int mid, int high) {
//创建一个跟传进来数据个数相同长度的临时数组
int[] arrTemp = new int[high - low + 1];
//定义三个指针
int left = low;
int right = mid + 1;
int temp = 0;
while (left <= mid && right <= high) {
if (arr[left] < arr[high]) {
//左边的小,放入临时数组中
arrTemp[temp] = arr[left];
//指针右移
temp++;
left++;
} else {
//右边的小,放入临时数组中
arrTemp[temp] = arr[right];
//指针右移
temp++;
right++;//
}
}
//循环结束,总有一边是先把数装完的,还剩一部分
while (left <= mid) {
arrTemp[temp] = arr[left];
//指针右移
temp++;
left++;
}
while (right <= high) {
arrTemp[temp] = arr[right];
//指针右移
temp++;
right++;//
}
//讲排好序的临时数组放回原数组中
for (int i = 0; i < arrTemp.length; i++) {
arr[low] = arrTemp[i];
low++;
}
}