// 堆排序
public static void heapSort(int[] arr) {
int temp = 0;
for(int i=arr.length/2-1; i>=0; i--) {
arryToHeap(arr, i, arr.length);
}
for(int j=arr.length-1; j>0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
arryToHeap(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
// 二叉树调整成大顶堆
// i -> 非叶子节点在数组中的索引
// len -> 表示对多少个元素进行调整
public static void arryToHeap(int[] arr, int i, int len) {
int temp = arr[i];
for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
if(k+1 < len && arr[k] <arr[k+1]) { //左子点小于右子点
k++;
}//结束后k指向于更大的值
if(arr[k] > temp) { //如果子节点大于父节点
arr[i] = arr[k];
i = k;
} else{
break;
}
}
arr[i] = temp;
} // 堆排序
public static void heapSort(int[] arr) {
int temp = 0;
for(int i=arr.length/2-1; i>=0; i--) {
arryToHeap(arr, i, arr.length);
}
for(int j=arr.length-1; j>0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
arryToHeap(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
// 二叉树调整成大顶堆
// i -> 非叶子节点在数组中的索引
// len -> 表示对多少个元素进行调整
public static void arryToHeap(int[] arr, int i, int len) {
int temp = arr[i];
for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
if(k+1 < len && arr[k] <arr[k+1]) { //左子点小于右子点
k++;
}//结束后k指向于更大的值
if(arr[k] > temp) { //如果子节点大于父节点
arr[i] = arr[k];
i = k;
} else{
break;
}
}
arr[i] = temp;
} 
***排序都是从小到大排序***
冒泡排序
图解：
第一轮：
| 30 | 12 | 4 | 5 | 3 |
| 12 | 30 | 4 | 5 | 3 |
| 12 | 4 | 30 | 5 | 3 |
| 12 | 4 | 5 | 30 | 3 |
| 12 | 4 | 5 | 3 | 30 |
| 12 | 4 | 5 | 3 | 30 |
| 4 | 12 | 5 | 3 | 30 |
| 4 | 5 | 12 | 3 | 30 |
| 4 | 5 | 3 | 12 | 30 |
| 4 | 5 | 3 | 12 | 30 |
| 4 | 3 | 5 | 12 | 30 |
| 4 | 3 | 5 | 12 | 30 |
| 4 | 3 | 5 | 12 | 30 |
| 3 | 4 | 5 | 12 | 30 |
public static void main(String[] args) {
int[] array = {-1, -5, 30, 12, 4, 5, 3, -10, -100, -109};
int size = array.length;
for(int i=0; i<size-1; i++) {
for(int j=0; j<size-i-1; j++) {
if(array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
for(int i=0; i<size; i++) {
System.out.print(array[i] + " ");
}
} 简单选择排序
说明：选择数组中最小的元素放到第一个位置，从第二个位置开始数组中选择最小的元素放到第二个位置，以此类推。
图解：
加粗的数字为需要交换的数字，加上下划线的数字为要交换的数字应该到的位置。
| 12 | 5 | 4 | 3 |
| 3 | 5 | 4 | 12 |
| 3 | 4 | 5 | 12 |
| 3 | 4 | 5 | 12 |
for (int i = 0; i < size - 1; i++) {
int min = array[i]; //假设最小值
int minIndex = i; //假设最小值的位置
for (int j = i + 1; j < size; j++) { //寻找最小值
if (min > array[j]) {
min = array[j];
minIndex = j;
}
}
//交换最小值
array[minIndex] = array[i];
array[i] = min;
} 直接插入排序
图解：
带括号的为有序数组，起始有序数组只有一个元素
| （12） | 4 | 5 | 3 |
| （4 | 12） | 5 | 3 |
| （4 | 5 | 12） | 3 |
| （3 | 4 | 5 | 12） |
for (int i = 1; i < size; i++) {
int insertValue = array[i]; //要插入的值
int insertIndex = i - 1; //要第一次插入的位置
while (insertIndex >= 0 && insertValue < array[insertIndex]) { //寻找要插入的元素的位置
array[insertIndex + 1] = array[insertIndex]; //后移操作
insertIndex--;
}
array[insertIndex + 1] = insertValue; //要插入的元素插入到相应位置
} 根据代码图解直接插入排序算法 原始数组：12, 4, 5, 3第一次循环(到while循环刚结束)：12, 12, 5, 3 //这个就是在while循环里执行的后移操作第一次循环(执行 array[insertIndex + 1] = insertValue语句之后)：4,12,5,3
缺点：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。所以提出解决方案---希尔排序。
希尔排序
说明：在插入排序的基本思想上进行优化。按下标的一定增量进行分组，对每组使用直接插入排序算法，随着增量的减少，魅族包含的关键词越多，当增量减少到1的时候最整体进行插入排序即可。 图解：
就是根据上图思路进行排序，用代码实现的时候有交换数字排序和移动数字排序两种实现方法。
// 交换希尔排序，效率不高
public static void ShellSwapSort(int[] arr) {
int size = arr.length;
for (int gap = size / 2; gap > 0; gap /= 2) { //决定增量
for (int i = gap; i < size; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
// 希尔排序移动法，效率高
public static void ShellMoveSort(int[] arr) {
int size = arr.length;
for (int gap = size / 2; gap > 0; gap /= 2) { //决定增量
for (int i = gap; i < size; i++) { //对每组进行排序
int j=i;
int temp = arr[i];
if(arr[j] < arr[j - gap]) {
while(j-gap >=0 && temp < arr[j-gap]) {
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
}
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];
t += 1;
i += 1;
}else {
temp[t] = arr[j];
t += 1;
j += 1;
}
}
while(i <= mid) {
temp[t] = arr[i];
t += 1;
i += 1;
}
while(j <= right) {
temp[t] = arr[j];
t += 1;
j += 1;
}
t = 0;
int templeft = left;
while(templeft <= right) {
arr[templeft] = temp[t];
t += 1;
templeft += 1;
}
} 基数排序
说明：桶排序的一种扩展模式，基数排序的实现速度最快，不过占用的额外空间很多，当数据很多时会占用很多空间。堆排序
基本思想：
1，将待排序序列构造成一个大顶堆。
2，此时，整个序列的最大值就是堆顶的根节点。
3，将其与末尾元素进行交换，此时末尾就为最大值。
4，然后将剩余n-1个元素重新构造成一个堆，这样就会得到n-1个元素的次小值。如此反复执行，就能得到有序序列。
5，升序排序用需要构建大顶堆，降序排序需要排序小顶堆。
6，整个排序过程都是在数组里执行，并非在二叉树上执行，不过为了好理解模拟成在二叉树上执行。
图解：
~第一次无序列表（再次强调整个排序都是在数组里执行，并非在二叉树里执行。）：
| 4 | 6 | 8 | 5 | 9 |
~调整第一个非叶子节点（非叶子几点的索引：array.length / 2 - 1 = 5 / 2 - 1 = 1）。所以要第一个调整的非叶子节点的小标为1，值为6。
调整后至》》》
| 4 | 9 | 8 | 5 | 6 |
~找到第二个非叶子节点（4为非叶子节点，由于[4,9,8]构成的二叉树为非大顶堆，所以调整至大顶堆）
| 9 | 4 | 8 | 5 | 6 |
~此时调整完之后发现由[4,5,6]组成的二叉树不能构成大顶堆，所以需要进行调整。
| 9 | 6 | 8 | 5 | 4 |
此时完整的构成大顶堆。
之后将堆顶元素于末尾元素进行交换，使末尾元素最大。之后排除末尾元素，在剩下的元素中找到最大，放到末尾元素前。反复进行交换，重建。就能得到有序数组。(此步骤为代码中的A部分)
// 堆排序
public static void heapSort(int[] arr) {
int temp = 0;
for(int i=arr.length/2-1; i>=0; i--) {
arryToHeap(arr, i, arr.length);
}
//A部分
for(int j=arr.length-1; j>0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
arryToHeap(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
// 二叉树调整成大顶堆
// i -> 非叶子节点在数组中的索引
// len -> 表示对多少个元素进行调整
public static void arryToHeap(int[] arr, int i, int len) {
int temp = arr[i];
for (int k = i * 2 + 1; k < len; k = k * 2 + 1) {
if(k+1 < len && arr[k] <arr[k+1]) { //左子点小于右子点
k++;
}//结束后k指向于更大的值
if(arr[k] > temp) { //如果子节点大于父节点
arr[i] = arr[k];
i = k;
} else{
break;
}
}
arr[i] = temp;
} 
京公网安备 11010502036488号