排序
交换排序
1.冒泡排序
算法描述（下浮）：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
public static void bubbleSort(int[] arr){
int temp;//临时变量
boolean flag=false;//标识变量，表示是否进行过交换
// 趟数是arr.length-1
for (int i = 0; i <arr.length-1 ; i++) {//趟数
//比较次数随着每一趟确定一个位置而递减arr.length-1-i
for (int j = 0; j <arr.length-1-i ; j++) {
// 升序
if (arr[j]>arr[j+1]){
flag=true;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
System.out.println("第"+(i+1)+"趟排序后的数组：");
System.out.println(Arrays.toString(arr));
if (!flag){
break;//在一趟排序中，一次交换都没有发生过
}else
flag=false;//重置flag，进行下次判断
}
}
2.快速排序
算法描述：
- 首先设置一个分界值也就是基准值，通过该分界值将数据分割成两部分。
- 将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素。
- 然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
当左右两部分都有序时，整个数据就完成了排序。
public static void quickSort(int[] arr, int left, int right) {
if (left >= right)
return;
int l = left, r = right;
int pivot = arr[left];
// 目的是左边比pivot小
// 目的是右边比pivot大
while (l < r) {
// 找到比pivot小于等于的数，才退出
while (l < r && arr[r] >= pivot)
r--;
// 将右边小于pivot位置的值赋值到左边
if (l < r)
arr[l] = arr[r];
// 找到比pivot大于等于的数，才退出
while (l < r && arr[l] <= pivot)
l++;
// 将左边大于pivot位置的值赋值到右边位置
if (l < r)
arr[r] = arr[l];
// 一轮排序结束
if (l >= r)
arr[l] = pivot;
}
quickSort(arr, left, r - 1);
quickSort(arr, l + 1, right);
}
选择排序
1.简单选择排序
算法描述：
- 先假定当前数为最小数
- 然后和后面的每个数进行比较，如果比较发现有比当前数更小的数，就重新确定最小数，并得到其下标
- 当遍历到数组的最后时，就得到了本轮最小数和下标
- 重复以上步骤，直到排序完成
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];//假定当前值就是最小值
// 将当前最小值0和后面1-n-1的数比较
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {//说明假定最小值并不是最小的
min = arr[j];//重置min
minIndex = j;//重置minIndex
}
}
// 将最小值，放置arr[0]即交换
if (minIndex != i) {//下标不等则交换
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println("第"+(i+1)+"轮排序后的数组");
System.out.println(Arrays.toString(arr));
}
}
插入排序
1.直接插入排序
算法描述：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 定义待插入数
int insertVal = arr[i];
int insertIndex = i - 1;//即arr[1]的前面这个数的下标
// 给insertVal找到插入的位置
/*
insertIndex>=0保证在给insertVal找插入位置不越界
insertVal< arr[insertIndex] 待插入的数和前一个数进行比较，还没有找到插入的位置
就需要将arr[insertIndex]的值后移
*/
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
// 因为当前的数小于前一个数，但是如果前一个数前面还有数，就要进一次进行比较
insertIndex--;
}
// 退出while循环，说明插入的位置找到了，insertIndex+1
if (insertIndex+1!=i)//如果待插入的数大于前一个数则无需移动
arr[insertIndex + 1] = insertVal;
System.out.println("第" + (i) + "趟排序后的数组：");
System.out.println(Arrays.toString(arr));
}
}
2.希尔排序
算法描述：
先选定一个整数gap，把待排序文件中所有记录分成数组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后缩小gap，重复上述步骤，当gap == 1时，所有记录在统一组内已经排好序。
1.交换式(算法没有得到提升)
// 交换式的希尔排序
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 第一轮排序，是将10个数据分为了5组
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素（共gap组，每组有个元素），步长gap
for (int j = i - gap; j >= 0; j -= gap) {
// 如果当前元素大于加上步长的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println("希尔排序第" + (++count) + "轮排序后的数组= " + Arrays.toString(arr));
}
}
2.移位式
// 移位式的希尔排序
public static void shellSort02(int[] arr){
for (int gap=arr.length/2;gap>0;gap/=2){
for (int i = gap; i <arr.length ; i++) {
int j=i;
int temp=arr[j];
if (arr[j]<arr[j-gap]){
while (j-gap>=0&&temp<arr[j-gap]){
arr[j]=arr[j-gap];
j-=gap;
}
// 退出while，就给temp找到了插入的位置
arr[j]=temp;
}
}
}
}
归并排序
算法描述：
- 分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
- 合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
- 先把左右两边（有序）的数据按照规则填充到temp数组
直到左右两边的有序序列，有一边处理完毕为止 - 然后将有剩余数据的一边的数据依次全部填充到temp
- 将temp数组的元素拷贝到arr
- 先把左右两边（有序）的数据按照规则填充到temp数组
// 分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;//中间索引
// 向左递归分解
mergeSort(arr, left, mid, temp);
// 向右递归分解
mergeSort(arr, mid + 1, right, temp);
// 合并
merge(arr,left,mid,right,temp);
}
}
/**
* @param arr 待排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 左中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;// 初始化i，左边有序序列的初始索引
int j = mid + 1;// 初始化j，右边有序序列的初始索引
int t = 0;// 指向temp数组的当前索引
/*
一
先把左右两边（有序）的数据按照规则填充到temp数组
直到左右两边的有序序列，有一边处理完毕为止
*/
while (i <= mid && j <= right) {
// 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
// 即将左边的当前元素，到temp数组
// 然后t++,i++
if (arr[i] < arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
// 如果左边的有序序列的当前元素，大于等于右边有序序列的当前元素
// 即将右边的当前元素，到temp数组
// 然后t++,j++
temp[t] = arr[j];
t++;
j++;
}
}
//二
// 将有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) {//左边的有序序列还有剩余元素，就全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {//右边的有序序列还有剩余元素，就全部填充到temp
temp[t] = arr[j];
t++;
j++;
}
//三
// 将temp数组的元素拷贝到arr
// 并不是每次拷贝是拷贝所有的元素
t = 0;
int tempLeft = left;
// 第一次合并tempLeft=0，right=1;第二次合并tempLeft=2，right=3;
// 最后一次合并tempLeft=0，right=arr.length-1
System.out.println("tempLeft= "+tempLeft+" right= "+right);
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
基数排序
算法描述：
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
// 基排序
public static void radixSort(int[] arr) {
// 得到数组中最大的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max)
max = arr[i];
}
// 得到最大数几位数
int maxLength = (max + "").length();
// 第一轮(针对每个元素得个位进行排序处理)
// 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
// 二维数组包含10个一维数组
// 为了放置在放入数的时候，数据溢出，每一个一维数组，大小定为arr.length
// 基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
// 为了记录每个桶中，实际存放了多少个数据，定义一个一维数组记录各个桶的每次放入的数据个数
//比如bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
int[] bucketElementCounts = new int[arr.length];
for (int i = 0, n = 1; i < maxLength; i++,n *= 10) {
// 每一轮(针对每个元素的对应位进行排序处理) 第一次十位...
for (int j = 0; j < arr.length; j++) {
// 取出每个元素的对应的值
int digitOfElement = arr[j] / n % 10;
// 放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照这个桶的顺序（一维数组的下标依次取出数据，放入原数组）
int index = 0;
// 遍历每一个桶，并将桶中的数据，放入原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中有数据，才放入到原数组
if (bucketElementCounts[k] != 0) {
// 循环该桶即第k个桶（即第k个一维数组），放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入arr
arr[index++] = bucket[k][l];
}
}
// 第i+1轮处理后，需要将每个bucketElementCounts[k] = 0！！！;
bucketElementCounts[k] = 0;
}
}
System.out.println("排序后的处理arr = \n" + Arrays.toString(arr));
}