基本排序算法的实现，包括选择排序，插入排序，冒泡排序，希尔排序，归并排序，堆排序，快速排序
选择排序
思想：从第一个记录开始，进行一轮比较后，得到最小记录，然后将其与第一个记录交换，对不包括第一个记录的剩余记录进行比较，直至所有记录有序
复杂度：O(n^2)
不稳定
public static void selectSort(int arr[]) {
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];//记录最小的数
int flag = i;//记录最小的数的位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < temp) {
temp = arr[j];// 找出最小值
flag = j;// 记录最小值位置
}
}
if (flag != i) {// 交换数据
arr[flag] = arr[i];
arr[i] = temp;
}
}
}插入排序
思想：按照记录的大小依次将当前处理的记录插入到之前的有序序列中，直至最后一个序列插入到有序序列为止（类似两个指针）
复杂度：O(n^2)
稳定
public static void insertSort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
if (arr[j - 1] > temp) {
while (j >= 1 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];//小的数前移
j--;
}
}
arr[j] = temp;
}
}
冒泡排序
思想：从第一个记录开始，依次对相邻两个记录进行比较，若前记录大于后记录，交换位置。进行一轮比较和换位后，n个记录最大的将位于第n位，然后对（n-1）个记录进行比较只剩下一个为止.(最大的会一直向后走，所以每比较完一次就减少1个比较个数)
复杂度：O(n^2)
稳定
public static void bubbleSort(int[] arr) {
int n = arr.length;
int a = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
System.out.println("第" + a + "交换：");
ArrayDemo.printArray(arr);
a++;
}
}
}
}希尔排序
思想：将序列分为多个子序列，是每个子序列的元素相对较少，然后对每个子序列进行直接插入排序，待每个子序列基本有序后，在对所有元素进行直接插入排序
复杂度：O(n^s) 1
public static void shellSort(int arr[]) {
int i, j, h, temp;
for (h = arr.length / 2; h > 0; h = h / 2) {// 确定所选的分组2 1
for (i = h; i < arr.length; i++) {// 从分割的位置开始操作
temp = arr[i];
for (j = i - h; j >= 0; j -= h) {// 向与后面的比较
if (temp < arr[j]) {
arr[j + h] = arr[j];// 相隔h个单位交换
} else {
break;// 最终都是两两相比，若不交换则没必要再循环下去
}
}
arr[j + h] = temp;
}
}
}归并排序
思想：对于给定的一个记录，首先将每两个相邻的长度为1的子序列进行合并，得到n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行
复杂度：O(nlogn)
关键步骤：
1：划分半字表
2：合并半子表
稳定
public static void mergeSort(int arr[], int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);// 排序左半部分
mergeSort(arr, q + 1, r);// 排序右半部份
merge(arr, p, q, r);// 合并子表
}
}
private static void merge(int arr[], int p, int q, int r) {
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
int[] left = new int[n1];
int[] right = new int[n2];
for (i = 0, k = p; i < n1; i++, k++) {// 复制左半部分
left[i] = arr[k];
}
for (i = 0, k = q + 1; i < n2; i++, k++) {// 复制右半部份
right[i] = arr[k];
}
for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {
if (left[i] > right[j]) {
arr[k] = right[j];
j++;
} else {
arr[k] = left[i];
i++;
}
}
if (i < n1) {
for (j = i; j < n1; j++, k++) {// 左半部分还剩余
arr[k] = left[j];
}
}
if (j < n2) {
for (i = j; i < n2; i++, k++) {// 右半部份还剩余
arr[k] = right[i];
}
}
}堆排序
思想：将数组A创建为一个最大堆，然后交换堆的根(最大元素)和最后一个叶节点x，将x从堆中去掉形成新的堆A1，然后重复以上动作，直到堆中只有一个节点。
复杂度：O(nlogn)
不稳定
public static void heapSort(int[] arr) {
int i;
int n = arr.length;
for (i = n / 2 - 1; i >= 0; i--) {
adjustMaxHeap(arr, i, n - 1);// 初始化堆
System.out.println("初始化交换：");
ArrayDemo.printArray(arr);
}
for (i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
adjustMaxHeap(arr, 0, i - 1);// 调整堆
System.out.println("交换：");
ArrayDemo.printArray(arr);
}
}
@SuppressWarnings("unused")
private static void adjustMinHeap(int[] arr, int pos, int len) {
int child;
int temp;
for (temp = arr[pos]; 2 * pos + 1 <= len; pos = child) {
child = 2 * pos + 1;
if (child < len && arr[child] > arr[child + 1]) {
child++;
}
if (arr[child] < temp) {
arr[pos] = arr[child];
} else {
break;
}
}
arr[pos] = temp;
}
private static void adjustMaxHeap(int[] arr, int pos, int len) {
int child;
int temp;
for (temp = arr[pos]; 2 * pos + 1 <= len; pos = child) {
child = 2 * pos + 1;
if (child < len && arr[child] < arr[child + 1]) {
child++;
}
if (arr[child] > temp) {//始终将目标结点与子节点比较。如果比最大子节点小，交换
arr[pos] = arr[child];
} else {//如果父节点比最大子节点大，说明不必做操作
break;
}
}
arr[pos] = temp;//最后将目标结点放在最后交换的子节点位置，此时的pos=child
}快速排序
思想：对于一组记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的记录小，然后依次对前后两部分的记录进行快排，递归该过程，直至所有记录有序
复杂度：O(n^2)
不稳定
步骤：
1.分解
2.递归求解
3.合并
public static void quickSort(int arr[]) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int arr[], int low, int high) {
int i, j, key;
if (low >= high) {
return;
}
i = low;
j = high;
key = arr[i];
while (i < j) {
while (i < j && arr[j] >= key) {// 从j右向左找到小于key的记录
j--;
}
if (i < j) {// 找到就交换，并且i向右走
arr[i++] = arr[j];
}
while (i < j && arr[i] < key) {// 从i左向右找到大于key的记录
i++;
}
if (i < j) {// 找到就交换，并且j向左走
arr[j--] = arr[i];
}
}
System.out.println(arr[i]);
arr[i] = key;// 交换后将key赋值到最后交换完成的位置，以此种方式减少交换次数，此时i=j
ArrayDemo.printArray(arr);
// 以i为中间分界线递归
sort(arr, low, i - 1);
sort(arr, i + 1, high);
}经过整理与思考之后，这几个排序算法思想基本已经完全理解了，发现其实不难，但是如果不复习笔试的时候很容易慌乱忘记（大神勿喷），小白在此与大家共勉