1 冒泡排序
冒泡排序：通过对待排序序列从前向后，依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前向后移。若排序一趟比较下来没有进行过交换，则序列有序，排序完成。其平均时间复杂度为
。
冒泡排序
代码实现：
//冒泡排序
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};
int temp = 0;//用于数据交换的临时变量
boolean flag = false;//判断是否进行过交换，若未发生交换则已有序，无需继续进行排序
for (int i = 0; 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) + "趟排序后的结果为：" + Arrays.toString(arr));
if (!flag) {
break;
} else {
flag = false;
}
}
}
}
执行结果如下：
冒泡排序执行结果
2 选择排序
选择排序是按照指定的规则选出某一元素，再依规定交换位置后达到排序的目的。平均时间复杂度为
基本流程：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
选择排序
代码实现：
//选择排序
public class SelectSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
int temp;//用于交换的临时变量
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//如果最小值位置改变则交换
if (i != min) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
System.out.println("第" + (i + 1) + "趟选择排序后的结果为：" + Arrays.toString(arr));
}
}
}
执行结果如下：
选择排序
3 插入排序
插入排序是对欲排序的元素以插入的方式寻找该元素的适当位置，以达到排序目的。类似于打扑克的时候对牌排序。
基本流程：
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
插入排序
代码实现：
//插入排序
public class InsertSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};
if (arr.length > 1) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];//要插入的数
int j = i - 1;//下一次要比对的索引
while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
if ((j + 1) != i) {
arr[j + 1] = temp;
}
System.out.println("第" + (i + 1) + "趟插入排序后的结果为：" + Arrays.toString(arr));
}
}
}
}
执行结果：
执行结果
4 希尔排序
希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
基本流程：
- 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序
实现代码：
//希尔排序
public class ShellSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};//待排序数组
//计算分组数
for (int group = arr.length / 2, num = 1; group > 0; group /= 2, num++) {
//从分组的后半部分开始对应比较
for (int i = group; i < arr.length; i++) {
int index = i; //记录当前的索引
int temp = arr[index]; //记录当前索引的值
//插入排序思想
while (index - group >= 0 && temp < arr[index - group]) {
arr[index] = arr[index - group];
index -= group;
}
arr[index] = temp;
}
System.out.println("第" + num + "趟希尔排序后的结果为：" + Arrays.toString(arr));
}
}
执行结果：
希尔排序
5 快速排序
快速排序是对冒泡排序的一种改进。
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。
基本流程：
- 从数列中挑出一个元素，称为 "基准"（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
快速排序
代码实现：
//快速排序
public class QuickSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};
quick(arr, 0, arr.length - 1);
System.out.println("快速排序后的结果为：" + Arrays.toString(arr));
}
public static void quick(int[] arr, int left, int right) {
int i = left; //左边指针往右
int j = right; //右边指针往左
int pivot;//这里使用左边值作为基准值
//将比pivot小的放到左边，比pivot大的放到右边
if (left < right) {
pivot = arr[left];
while (i < j) {
while (j > i && arr[j] > pivot) --j; //从右往左扫描，找到一个小于pivot的值
if (i < j) {
arr[i] = arr[j]; //此时i位置的值已存入pivot中
++i;
}
while (i < j && arr[i] < pivot) ++i;
if (i < j) {
arr[j] = arr[i]; //j位置的值已在之前存入i中
--j;
}
}
arr[i] = pivot;
quick(arr, left, i - 1);//递归排序左边
quick(arr, i + 1, right);//递归排序右边
}
}
}
执行结果：
执行结果
6 归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
有两种实现方法：
- 自上而下的递归；
- 自下而上的迭代；
基本流程：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
归并排序
public class MergeSort {
public static void main(String[] args) {
int arr[] = {3, 4, -6, 2, 9, 7, 0, 14};
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
System.out.println(Arrays.toString(arr));
}
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);
}
}
//合并
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[t] = arr[i];
i++;
} else {
temp[t] = arr[j];
j++;
}
t++;
}
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
t = 0;
while (left <= right) {
arr[left] = temp[t];
t++;
left++;
}
}
}
执行结果：
执行结果
