import java.util.Arrays;
/**
* 本代码的知识点:
* 冒泡排序
* 它重复地访问过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来
*/
public class Exer010Sort01BubbleSortV1 {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//记录比较次数
int count = 0;
//i=0,第一轮比较
for (int i = 0; i < a.length - 1; i++) {
//第一轮，两两比较
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
count++;
}
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比较了：" + count + "次");//一共比较了：105次
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 优化，减少排序次数
*/
public class Exer010Sort01BubbleSortV2 {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
int count = 0;
for (int i = 0; i < a.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = false;
}
count++;
}
if (flag) {
break;
}
}
System.out.println(Arrays.toString(a));// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println("一共比较了：" + count + "次");//一共比较了：95次
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 选择排序
* 先定义一个记录最小元素的下标，然后循环一次后面的，找到最小的元素，最后将他放到前面排序好的序列。
*/
public class Exer010Sort02SelectSort {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 0; i < a.length - 1; i++) {
int index = i;//标记第一个为待比较的数
for (int j = i + 1; j < a.length; j++) { //然后从后面遍历与第一个数比较
if (a[j] < a[index]) { //如果小,就交换最小值
index = j;//保存最小元素的下标
}
}
//找到最小值后，将最小的值放到第一的位置，进行下一遍循环
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 插入排序
* 定义一个待插入的数，再定义一个待插入数的前一个数的下标，然后拿待插入数与前面的数组一一比较，最后交换。
*/
public class Exer010Sort03InsertSort {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 0; i < a.length; i++) { //长度不减1，是因为要留多一个位置方便插入数
//定义待插入的数
int insertValue = a[i];
//找到待插入数的前一个数的下标
int insertIndex = i - 1;
while (insertIndex >= 0 && insertValue < a[insertIndex]) {//拿a[i]与a[i-1]的前面数组比较
a[insertIndex + 1] = a[insertIndex];
insertIndex--;
}
a[insertIndex + 1] = insertValue;
}
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 希尔排序
* 插入排序的升级
*/
public class Exer010Sort04ShellSort {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
int count = 0;//比较次数
for (int gap = a.length / 2; gap > 0; gap = gap / 2) {
//将整个数组分为若干个子数组
for (int i = gap; i < a.length; i++) {
//遍历各组的元素
for (int j = i - gap; j >= 0; j = j - gap) {
//交换元素
if (a[j] > a[j + gap]) {
int temp = a[j];
a[j] = a[j + gap];
a[j + gap] = temp;
count++;
}
}
}
}
System.out.println(count);//16
System.out.println(Arrays.toString(a));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 快速排序
*/
public class Exer010Sort05QuickSort {
public static void main(String[] args) {
//int a[]={50,1,12,2};
int a[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quicksort(a,0,a.length-1);
System.out.println(Arrays.toString(a));
}
private static void quicksort(int[] a, int low, int high) {
int i,j;
if (low>high) {
return;
}
i=low;
j=high;
int temp=a[low];//基准位,low=length时，会报异常，java.lang.ArrayIndexOutOfBoundsException: 4 ，所以必须在if判断后面,就跳出方法。
while(i<j){
//先从右边开始往左递减，找到比temp小的值才停止
while ( temp<=a[j] && i<j) {
j--;
}
//再看左边开始往右递增，找到比temp大的值才停止
while ( temp>=a[i] && i<j) {
i++;
}
//满足 i<j 就交换,继续循环while(i<j)
if (i<j) {
int t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最后将基准位跟 a[i]与a[j]相等的位置，进行交换,此时i=j
a[low]=a[i];
a[i]=temp;
//左递归
quicksort(a, low, j-1);
//右递归
quicksort(a, j+1, high);
}
}
import java.util.Arrays;
/**
* 本代码的知识点:
* 合并排序
*/
public class Exer010Sort06MergeSort {
public static void main(String[] args) {
int a[] = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//int a[]={5,2,4,7,1,3,2,2};
int temp[] = new int[a.length];
mergesort(a, 0, a.length - 1, temp);
System.out.println(Arrays.toString(a));
}
private static void mergesort(int[] a, int left, int right, int[] temp) {
//分解
if (left < right) {
int mid = (left + right) / 2;
//向左递归进行分解
mergesort(a, left, mid, temp);
//向右递归进行分解
mergesort(a, mid + 1, right, temp);
//每分解一次便合并一次
merge(a, left, right, mid, temp);
}
}
private static void merge(int[] a, int left, int right, int mid, int[] temp) {
int i = left; //初始i，左边有序序列的初始索引
int j = mid + 1;//初始化j，右边有序序列的初始索引（右边有序序列的初始位置即中间位置的后一位置）
int t = 0;//指向temp数组的当前索引，初始为0
//先把左右两边的数据（已经有序）按规则填充到temp数组
//直到左右两边的有序序列，有一边处理完成为止
while (i <= mid && j <= right) {
//如果左边有序序列的当前元素小于或等于右边的有序序列的当前元素，就将左边的元素填充到temp数组中
if (a[i] <= a[j]) {
temp[t] = a[i];
t++;//索引向后移
i++;//i后移
} else {
//反之，将右边有序序列的当前元素填充到temp数组中
temp[t] = a[j];
t++;//索引向后移
j++;//j后移
}
}
//把剩余数据的一边的元素填充到temp中
while (i <= mid) {
//此时说明左边序列还有剩余元素
//全部填充到temp数组
temp[t] = a[i];