排序算法
- 快速排序：
O( N Log N ) - 归并排序：
O( N Log N ) - 堆排序：
O( N Log N ) - 选择排序：
O( N^2 ) - 插入排序：
O( N^2 )
快速排序
基本思路：快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序；
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后:");
for (int i : arr) {
System.out.println(i);
}
}
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
//quickSort(arr, 0, index - 1); 之前的版本，这种姿势有很大的性能问题，谢谢大家的建议
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high{
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
}
归并排序
public class MergeSort {
// 分治+合并的思想
public static void main(String[] args) {
int[] arr = new int[]{10,6,5,8,9,2,8,4};
int L = 0, R = 7, M = 4;
//merge(arr, L, M, R);
mergeSort(arr, L, R);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
//将两个各自有序的数组合并成一个有序的
public static void merge(int[] arr, int L, int M, int R) {
//这里先默认数组两边各自有序，后面利用递归将数组一直拆分，拆到两边只有一个元素，一个元素先天有序
int LEFT_SIZE = M - L;
int RIGHT_SIZE = R - M + 1;
//定义两个新数组 将元素数组中间分成两个数组
int[] left = new int[LEFT_SIZE];
int[] right = new int[RIGHT_SIZE];
//将原数组左半部分 填入left数组
for (int i = L; i < M; i++) {
left[i - L] = arr[i];
}
//这里将 i 设置成 L和M，是方便从arr[]中取数据
//将原数组右半部分 填入right数组
for (int i = M; i <= R; i++) {
right[i - M] = arr[i];
}
//将两个数组 有序合并 到原始数组中
//i为left数组的索引，j为right数组的索引，k为合并到的原始数组的索引 (利用i ，j 不断比较两个数组，每次都将小的放进原始数组)
int i = 0, j = 0;
int k = L;
while (i < LEFT_SIZE && j < RIGHT_SIZE) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
k++;
} else {
arr[k] = right[j];
j++;
k++;
}
}
//如果 i 到了数组顶部，即left数组遍历完了，表示right数组的剩余元素都比left数组大，直接将right数组剩余元素放进arr[]原始数组即可【 j 同理】 总有一个数组先遍历完，后面直接将另一个数组接着遍历即可
while (i < LEFT_SIZE) {
arr[k] = left[i];
i++;
k++;
}
while (j < RIGHT_SIZE) {
arr[k] = right[j];
j++;
k++;
}
}
//分治
//上面的merge()函数是将两个各自有序的数组合并，对于全部无序的数组，可以利用递归，将其分解，最终分到序列为1，则先天有序
public static void mergeSort(int[] arr, int L, int R) {
//递归
if(L == R) { //递归终止条件: 分到左右都为 1 个元素，
return;
} else {
int M = (L + R) / 2; //分成两半
//递归分半
mergeSort(arr, L , M);
mergeSort(arr, M+1, R);
//两边默认有序，合并即可
merge(arr, L,M+1, R);
}
}
}
堆排序
- 堆的两个条件
- 完全二叉树 （结点生成顺序：从上到下，从左到右）
- 满足所有的 父结点 > 子结点
几棵完全二叉树
heapify()函数：交换结点，将树变成： 父结点 > 子结点
构建堆
public class HeapSort{
//验证
public static void main(String[] args) {
int tree[] = new int[]{2, 5, 3, 1, 10, 4};
//堆排序
heap_sort(tree, 6);
for(int i = 0; i < tree.length; i++) {
System.out.println(tree[i]);
}
}
//对创建好的堆进行排序
public static void heap_sort(int tree[], int n) {
//创建堆
build_heap(tree, n);
//排序: 每次都将 根节点(最大值) 与 最后一个结点(i 表示的就是当前树的结点总数，不断减少)进行交换,然后将最大的根结点取出，对对新根结点所在树做heapify()操作，重新构建堆结构
for(int i = n - 1; i >= 0; i--) {
swap(tree, i, 0);
//i 的减少即表示 去掉最大结点
heapify(tree, i, 0); //对新根结点所在树做heapify()
}
}
//heapify(): 将树变成 父结点 > 子结点 tree[]: 树 n: 树的结点总数 i: 对哪一个结点做heapify()操作
public static void heapify(int tree[], int n, int i) {
//递归出口(递归调用heapify()时改变了 i 的值，i=n时遍历完成)
if(i >= n) {
return;
}
int c1 = 2 * i + 1; //子结点在数组中的下标
int c2 = 2 * i + 2;
int max = i;
if(c1 < n && tree[c1] > tree[max]) {
max = c1;
}
if(c2 < n && tree[c2] > tree[max]) {
max = c2;
}
if(max != i) {
swap(tree, max, i);
heapify(tree, n, max);// 递归地对下一层进行相同heapify()操作
}
}
//构建完整堆
public static void build_heap(int tree[], int n) { //n表示结点总数
//找到树的最后一个结点,往上递减,对上面的所有结点做heapify()
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for(int i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
public static void swap(int tree[], int i, int j) {
int temp = tree[i];
tree[i] = tree[j];
tree[j] = temp;
}
}