1、关于稳定性
不稳定: 快选堆希(快速排序、选择排序、堆排序、希尔排序)
稳 定: 插冒归计基(简单插入排序、冒泡排序、归并排序、计数排序、基数排序)
2、关于时间复杂度
平方阶 (O(n2)) 排序
各类简单排序:直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序
快速排序、堆排序和归并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数
希尔排序
线性阶 (O(n)) 排序
基数排序,此外还有桶、箱排序。
3、关于移动次数和关键字顺序无关的排序
堆排序、归并排序、选择排序、基数排序
In-place:占用常数内存,不占用额外内存
Out-place:占用额外内存
每次遍历,都将最大的元素移到最后。
相邻两个元素之间的比较。
public void bulbSort(int[] arr) {
// 当前个与后一个相比,所以外循环只需n-1次
for (int i = 0; i < arr.length-1; i++) {
// 内循环比较大小,因为当第i次循环完后,最后的i+1个已排完序,下一次可以不用参与
// 如:3 1 4 2
// 第i=0次循环完(4-1-0=3次):1 3 2 4,最后一个排完序,下一次可以不用参与
// 第i=1次循环完(4-1-1=2次):1 2 3 4,最后两个排完序,下一次可以不用参与
for (int j = 0; j < arr.length - i - 1; j++) {
// 相邻元素两两对比,如果第一个比第二个大,就交换他们两个
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
public void selectionSort(int[] arr) {
// 当前个与后一个相比,所以外循环只需n-1次
for (int i = 0; i < arr.length - 1; i++) {
// 每次循环,i前面的都是已经排完序了的
// 初始将当前i位置的数认为是最小的
int minIndex = i;
// 从i后面的所有数中,寻找值最小的数
for (int j = i+1; j < arr.length; j++) {
// 判断是否比当前已知的最小的数还要小
if (arr[j]<arr[minIndex]) {
// 将最小数的索引保存
minIndex = j;
}
}
// 如果两者不相等,说明存在比它更小的数,需要交换
if (i!=minIndex){
// 将i位置的数与最小值的数交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
依次将元素插入对应位置,不符合的元素后移。
在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
当前元素与它前面所有元素的对比。
public void insertSort(int[] arr) {
// 第i=0个元素默认已经是有序,因此从i=1开始
// 每个元素都要参与比较,所以arr[n]也要取到
for (int i = 1; i < arr.length; i++) {
// 先记录下待插入的元素的值
int key = arr[i];
int j;
// 在已排序中,从后往前扫描
// 依次对比大小,大于它的往后移动,直至找到正确位置后停止
// j=i-1:前i-1个元素已经是排完序了的
for (j = i-1; j>=0 && arr[j]>key; j--) {
arr[j+1] = arr[j];
}
// 将值插入,注意上面的for循环出来前会执行一次j--,所以这里要j+1
arr[j+1] = key;
}
}
使用分治法来把一个串(list)分为两个子串(sub-lists)。
左右指针相向移动,先从右指针开始;小的放左边,大的放右边。
挖坑法
public void quickSort(int[] arr, int left, int right) {
// 当left=right时,说明左右指针指向了同一个元素
// 即当前分组只有一个元素,递归结束
if (left>=right) {
return;
}else {
int l = left;
int r = right;
// 将左边第一个元素作为基准值
// 记录基准值,此时arr[l]这个位置可以放其他值了
int pivot = arr[l];
// 对于当前递归
// 循环比较,直至左右指针相遇,即l=r
while (l<r) {
// 先将右指针向左移动,直到遇到一个比基准值小的元素
while (l<r && arr[r]>pivot) {
r --;
}
// 如果指向了同一个元素,就不需要交换
// 否则,就需要交换
if (l<r) {
// 将右指针指向的元素值赋给左指针指向的元素值
// 此时arr[r]又可以存其他新的内容了
arr[l] = arr[r];
// 左指针已经填值,因此需要l++
l ++;
}
// 再将左指针向右移动,直到遇到一个比基准值大的元素
while (l<r && arr[l]<pivot) {
l ++;
}
// 同上,下同
if (l<r) {
arr[r] = arr[l];
r --;
}
}
// 此时l=r,说明左右指向了同一个位置
// 而这个位置应该放的是基准值,且一趟排序完成
arr[l] = pivot;
// 对基准值左边部分再进行递归排序
quickSort(arr, left, l-1);
// 对基准值右边部分再进行递归排序
// 由于此时l=r,所以r+1=l+1没影响
quickSort(arr, r+1, right);
}
}
先拆分,再合并排序的算法
/**
* 合并排序部分
* @param arr 原始数组
* @param tempArr 临时数组
* @param left 当前分组的左边位置序号
* @param right 当前分组的右位置边序号
*/
public void merge(int[] arr, int[] tempArr, int left, int right) {
// 大于1个元素,还可继续划分
if (left < right) {
// 中间位置
int mid = (left+right)/2;
// 左半部分递归划分
merge(arr, tempArr, left, mid);
// 右半部分递归划分
merge(arr, tempArr, mid+1, right);
// 到这里,说明已经划分完,开始向上合并
// 指向左边组序列的第一个
int l = left;
// 指向右边组序列的第一个
int r = mid+1;
// 临时数组的下标,这里的临时数组是存排序后的元素,排完后再复制到原数组中
int tempIndex = left;
// 循环比较,直至左边组或右边组没有剩余元素了才停止
while (l<=mid && r<=right) {
// 可以想象最简单的情况,倒数第二层,有两个元素,需要对这两个元素排序
// 如果左边组的一个元素 < 右边组的一个元素,就将小的那个先放到临时数组中。放完后,下标+1指向下一个元素
if(arr[l]<arr[r]) {
tempArr[tempIndex++] = arr[l++];
}else {
tempArr[tempIndex++] = arr[r++];
}
}
// 可能左边组还有剩余元素,将剩余元素添加到临时数组最后
while (l<=mid) {
tempArr[tempIndex++] = arr[l++];
}
// 可能右边组还有剩余元素,将剩余元素添加到临时数组最后。这里与上面左边剩余的情况不会同时成立
while (r<=right) {
tempArr[tempIndex++] = arr[r++];
}
// 最后将排完顺序的临时数组中的元素复制到原数组中
while (left<=right) {
arr[left] = tempArr[left];
left++;
}
}
// 否则,说明已经划分到最小单元,即一个元素
else {
return;
}
}
public void mergeSort(int[] arr) {
// 开辟一个临时数组
int[] tempArr = new int[arr.length];
// 开始归并排序
merge(arr, tempArr, 0, arr.length-1);
}
public static void main(String[] args) {
int[] arr = new int[]{5,9,1,4,54,6,77,54,3,9,5,66,2,6,34};
new Main().mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
平均时间复杂度:O(nlogn) 最佳时间复杂度:O(n) 最差时间复杂度:O(nlogn) 空间复杂度:O(n) 排序方式:In-place 稳定性:稳定
不管元素在什么情况下都要做这些步骤,所以花销的时间是不变的,所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为:O( nlogn )
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间:n + logn
;所以空间复杂度为: O(n)
。
归并排序算法中,归并最后到底都是相邻元素之间的比较交换,并不会发生相同元素的相对位置发生变化,故是稳定性算法。
按组(增量)进行插入排序的算法。
通过对每组使用直接插入排序,使整个数组基本有序.数据有序程度越高,最后使用的插入排序效率越高。
动图是分组执行,实际操作是多个分组交替执行
当gap=4时,意味着将数列分为4个组: {80,20},{30,10},{60,50},{40,70}。 对应数列: {80,30,60,40,20,10,50,70}
对这4个组分别进行排序,排序结果: {20,80},{10,30},{50,60},{40,70}。 对应数列: {20,10,50,40,80,30,60,70}
当gap=2时,意味着将数列分为2个组:{20,50,80,60}, {10,40,30,70}。 对应数列: {20,10,50,40,80,30,60,70}
注意:{20,50,80,60}实际上有两个有序的数列{20,80}和{50,60}组成。
{10,40,30,70}实际上有两个有序的数列{10,30}和{40,70}组成。
对这2个组分别进行排序,排序结果:{20,50,60,80}, {10,30,40,70}。 对应数列: {20,10,50,30,60,40,80,70}
当gap=1时,意味着将数列分为1个组:{20,10,50,30,60,40,80,70}
注意:{20,10,50,30,60,40,80,70}实际上有两个有序的数列{20,50,60,80}和{10,30,40,70}组成。
对这1个组分别进行排序,排序结果:{10,20,30,40,50,60,70,80}
public void shellSort(int[] arr) {
// 每次增量除2
for (int inc = arr.length/2; inc > 0; inc/=2) {
// 每一趟使用插入排序,从第1组的第2个元素开始,到数组的最后一个元素
// 这里每趟都是对下一组进行排序,即各组交替执行,而不是一个组排序完后再换下一个组
for (int i = inc; i < arr.length; i++) {
// 先拿到当前位置的值key
int key = arr[i];
int j;
// 对当前组的当前位置及前面元素进行插入排序
// j>=inc:保证j-inc非负
// key<arr[j-inc]:将目标值与前一个元素的值比较
// j-=inc:指向当前组的前一个元素
for (j = i; j>=inc&&key<arr[j-inc]; j-=inc) {
// 将值后移
arr[j] = arr[j-inc];
}
// 将key插入,注意上面的for循环出来前,会执行一次j-=inc
arr[j] = key;
// 或者
/*
for (j = i-inc; j>=0 && arr[j]>key; j-=inc) {
arr[j+inc] = arr[j];
}
arr[j+inc] = key;
*/
}
}
希尔排序的时间复杂度与增量(即,步长gap)的选取有关。例如,当增量为1时,希尔排序退化成了直接插入排序,此时的时间复杂度为O(N²),而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。 复杂性:O(nlog(n))~O(n*n) 稳定性:不稳定
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
下标为i的节点的父节点下标:
(i-1)/2
【整数除法】 下标为i的节点的左孩子下标:i*2+1
下标为i的节点的右孩子下标:i*2+2
/**
* 堆排序
* @param arr 待排序数组
* @param n 总节点数
* @param i 当前节点的下标
*/
void heapify(int[] arr, int n, int i) {
// 记录最大值的节点的下标
int largest = i;
// 第i个节点的左子节点的下标:i*2+1
int lson = i*2+1;
// 第i个节点的右子节点的下标:i*2+2
int rson = i*2+2;
// 先比较根节点与左子节点的大小
// 如果左子节点的值更大,就记录左子节点的下标
if (lson<n && arr[lson]>arr[largest]) {
largest = lson;
}
// 再比较根节点(或左子节点,如果上面的if成立的话)与右子节点的大小
// 如果右子节点的值更大,就记录右子节点的下标
if (rson<n && arr[rson]>arr[largest]) {
largest = rson;
}
// 若不相等,则说明largest有变动过,即左或右子节点比根节点大了
if (largest != i) {
// 交换两者的值,把更大的值放到根节点上
int temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
// 递归执行堆维护,因为可能本次调整完后,影响了后面的堆性质,如:
// 3 4
// / \ / \
// 4 1 => 3 1
// / \ / \
// 5 2 5 2
// 3跟4换完后,3跟5也需要换
heapify(arr, n, largest);
}
}
/**
* 大顶堆,堆排序
* @param arr 待排序的数组
*/
public void heapSort(int[] arr) {
int n = arr.length;
// 1.建堆
// 第i个节点的根节点的下标:(i-1)/2
// 最后一个节点的根节点的下标:((n-1)-1)/2 = n/2-1
// 从最后一个根节点到0号根节点依次循环
for (int i = n/2-1; i >= 0; i--) {
// 从下往上维护堆,递归次数少,效率高
heapify(arr, n, i);
}
// 2.排序
// 将最大放到最后
// 由于大顶堆,所以最大值总是在0号节点上
// 从最后一个节点到0号节点依次循环
for (int i = n-1; i > 0; i--) {
// 交换两者的值,把最大值放到后面的节点上
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 交换完成后,对剩余的节点继续执行堆维护
// i: 由于每次都把最大值往后面放,所以这个i可以限制heapify不会影响到后面已排完序的节点
// 0: 从上往下维护堆,之前已经建完堆,这次可能只需要微调
heapify(arr, i, 0);
}
优点
缺点
应用领域
节点 | 含义 |
---|---|
(i - 1)/ 2 | 父节点 |
2*i+1 | 左子节点 |
2*i+2 | 右子节点 |
优点
缺点
应用领域
优点
缺点
应用领域
优点
应用领域
优点
缺点
应用领域
public class Node {
// 为了方便,变量都使用public,而不用private就不需要编写get、set方法了
public Node prev;
public Node next;
public int val;
// 无参构造方法
public Node() {}
// 构造方法,在构造时就能够给val赋值
public Node(int val) {
this.val = val;
}
}
public class LinkedList {
// 头结点
private Node head = new Node();
private int size = 0;
/**
* 打印链表
*/
public void print() {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
System.out.print(temp.val+"->");
}
System.out.println();
}
/**
* 返回链表大小
* @return 链表的大小
*/
public int getSize() {
return size;
}
/**
* 在链表最后添加节点
* @param val 待添加的值
*/
public void add(int val) {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(val);
size ++;
}
/**
* 在指定位置的插入节点,旧节点后移
* @param index 待添加的位置,第一个为0
* @param val 待添加的值
*/
public void insert(int index, int val) {
Node temp = head;
if (index<=size) {
// 遍历到待删除节点的前一个节点即可
for (int i = 0; i < index; i++) {
temp = temp.next;
}
Node node = new Node(val);
node.next = temp.next;
temp.next = node;
size ++;
}
}
/**
* 删除一个节点
* @param index 节点所在位置,第一个为0
*/
public void remove(int index) {
Node temp = head;
if (index<=size) {
// 遍历到待删除节点的前一个节点即可
for (int i = 0; i < index; i++) {
temp = temp.next;
}
// 重新链接,跳过待删除节点
temp.next = temp.next.next;
size --;
}
}
}
优点
缺点
应用领域
// 节点类
public class Node {
public int val;
public Node left;
public Node right;
public Node(int val) {
this.val = val;
}
}
public Node create() {
Node root = new Node(0);
root.left = new Node(1);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(5);
root.right.left.left = new Node(6);
return root;
}
/**
* 先序遍历,先输出根节点,再遍历左子节点,再遍历右子节点
* @param node
*/
public void preTraversal(Node node) {
if (node != null) {
System.out.print(node.val+" ");
preTraversal(node.left);
preTraversal(node.right);
}
}
/**
* 中序遍历,先遍历左子节点,再输出跟节点,再 遍历右子节点
* @param node
*/
public void midTraversal(Node node) {
if (node != null) {
midTraversal(node.left);
System.out.print(node.val+" ");
midTraversal(node.right);
}
}
/**
* 后序遍历
* @param node
*/
public void lastTraversal(Node node) {
if (node != null) {
lastTraversal(node.left);
lastTraversal(node.right);
System.out.print(node.val+" ");
}
}
/**
* 层序遍历
* 通过使用队列的数据结构,从树的根结点开始,依次将其左孩子和右孩子入队。
* 而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,
* 出队结点的先后顺序就是层次遍历的最终结果。
* @param root 根节点
*/
public void levelTraversal(Node root) {
// 先判断根节点非空
if (root!=null) {
// 创建一个队列(先入先出FIFO),用于存放节点
Queue<Node> queue = new LinkedList<>();
// 先将根节点放入
queue.offer(root);
// 然后取出一个节点
Node node = queue.poll();
// 循环取出、判断节点是否非空
while (node!=null) {
// 输出
System.out.print(node.val+" ");
// 判断左子节点非空,若非空则加入队列
if (node.left!=null) {
queue.offer(node.left);
}
// 判断右子节点非空,若非空则加入队列
if (node.right!=null) {
queue.offer(node.right);
}
// 从队列取出一个节点
node = queue.poll();
}
}
}
public static void main(String[] args) {
Node node = create();
preTraversal(node);
System.out.println();
midTraversal(node);
System.out.println();
lastTraversal(node);
System.out.println();
levelTraversal(node);
System.out.println();
}
优点
缺点
应用领域
public void insert(Node root, int value) {
// 当前节点不为空,则继续往下寻找
if (root != null) {
// 若待插入的值比当前节点的值小,则往左放
if (value < root.val) {
// 左子节点不为空,则递归插入
if (root.left != null) {
insert(root.left, value);
}
// 否则说明已到最后,可以插入
else {
root.left = new Node(value);
}
}
// 同上
else if (value > root.val) {
if (root.right != null) {
insert(root.right, value);
}else {
root.right = new Node(value);
}
}
}
// 当前节点为空,则直接赋值
else {
root = new Node(value);
}
}
优点
缺点
应用领域
优点
缺点
应用领域
从根节点开始,沿着树的宽度(横向,层)遍历树的节点。如果所有节点均被访问,则算法中止。如:
3
/ \
9 20
/ \
15 7
=> [ [3], [9,20], [15,7] ]
使用queue
队列的数据结构,具有先进先出FIFO
的特性。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<List<Integer>> levelOrder(TreeNode root) {
// 用于存最终结果
List<List<Integer>> ret = new ArrayList<>();
// 队列,用于存储节点信息
Queue<TreeNode> queue = new LinkedList<>();
if (root == null){
return ret;
}
// 先将head节点添加入队列,然后开始while循环。
queue.offer(root);
// 辅助作用的节点,用于指向出队的节点信息
TreeNode node;
while (!queue.isEmpty()){
// 临时的列表,存某一层的所有节点。
ArrayList<Integer> temp = new ArrayList<>();
// 得到队列的长度,此时队列的长度=这一层的节点数(后面可以发现)
int len = queue.size();
// 由于输出结果是二维数组结构,第二维的数组内数量就是该层的全部节点。
// 所以可以通过for循环填入某一层的所以节点。
for (int i = 0; i < len; i++) {
// 先出队第一个节点
node = queue.poll();
// 将该节点的值加入
temp.add(node.val);
// 如果左边子节点存在,则加入队列
if (node.left != null){
queue.offer(node.left);
}
// 如果右边子节点存在,则加入队列
if (node.right != null){
queue.offer(node.right);
}
}
// for循环完成,表示这一层的节点都已获取到,将此接入到结果列表中
ret.add(temp);
}
// 如果是倒序层次遍历,反转一下即可
Collections.reverse(ret);
return ret;
}
沿着树的深度(纵向)遍历树的节点,尽可能深的搜索树的分支。当节点的所在边都己被探寻过,搜索将回溯到发现节点的那条边的起始节点。
A
/ \
B C
/ \ / \
D E F G
=> A B C D E F G
使用stack
栈的数据结构,具有先进后出FILO
的特性。
操作步骤:
stack
stack
为空: stack
中访问栈顶的点stack
中stack
中弹出public void levelOrder(TreeNode root) {
// 创建一个栈
Stack<TreeNode> stack = new Stack<>();
// 临时节点
TreeNode treeNode;
// 先将head节点放入栈
stack.add(root);
// 循环,直至所有节点都处理完
while (!stack.isEmpty()){
// 弹出栈顶节点
treeNode = stack.pop();
// 获取节点的值
System.out.println(treeNode.val);
// 如果右边有节点,则入栈
// 注意“先入后出”特性,先入右边,先出左边,所以注意搜索顺序
if (treeNode.right != null){
stack.add(treeNode.right);
}
// 如果左边有节点,则入栈
if (treeNode.left != null){
stack.add(treeNode.left);
}
}
}
package com.sxf;
import java.util.Arrays;
public class Main {
public void bulbSort(int[] arr) {
// 当前个与后一个相比,所以外循环只需n-1次
for (int i = 0; i < arr.length-1; i++) {
// 内循环比较大小,因为当第i次循环完后,最后的i+1个已排完序,下一次可以不用参与
// 如:3 1 4 2
// 第i=0次循环完(4-1-0=3次):1 3 2 4,最后一个排完序,下一次可以不用参与
// 第i=1次循环完(4-1-1=2次):1 2 3 4,最后两个排完序,下一次可以不用参与
for (int j = 0; j < arr.length - i - 1; j++) {
// 相邻元素两两对比,如果第一个比第二个大,就交换他们两个
if (arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public void selectionSort(int[] arr) {
// 当前个与后一个相比,所以外循环只需n-1次
for (int i = 0; i < arr.length - 1; i++) {
// 每次循环,i前面的都是已经排完序了的
// 初始将当前i位置的数认为是最小的
int minIndex = i;
// 从i后面的所有数中,寻找值最小的数
for (int j = i+1; j < arr.length; j++) {
// 判断是否比当前已知的最小的数还要小
if (arr[j]<arr[minIndex]) {
// 将最小数的索引保存
minIndex = j;
}
}
// 如果两者不相等,说明存在比它更小的数,需要交换
if (i!=minIndex){
// 将i位置的数与最小值的数交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
public void insertSort(int[] arr) {
// 第i=0个元素默认已经是有序,因此从i=1开始
// 每个元素都要参与比较,所以arr[n]也要取到
for (int i = 1; i < arr.length; i++) {
// 先记录下待插入的元素的值
int key = arr[i];
int j;
// 在已排序中,从后往前扫描
// 依次对比大小,大于它的往后移动,直至找到正确位置后停止
// j=i-1:前i-1个元素已经是排完序了的
for (j = i-1; j>=0 && arr[j]>key; j--) {
arr[j+1] = arr[j];
}
// 将值插入,注意上面的for循环出来前会执行一次j--,所以这里要j+1
arr[j+1] = key;
}
}
public void quickSort(int[] arr, int left, int right) {
// 当left=right时,说明左右指针指向了同一个元素
// 即当前分组只有一个元素,递归结束
if (left>=right) {
return;
}else {
int l = left;
int r = right;
// 将左边第一个元素作为基准值
// 记录基准值,此时arr[l]这个位置可以放其他值了
int pivot = arr[l];
// 对于当前递归
// 循环比较,直至左右指针相遇,即l=r
while (l<r) {
// 先将右指针向左移动,直到遇到一个比基准值小的元素
while (l<r && arr[r]>pivot) {
r --;
}
// 如果指向了同一个元素,就不需要交换
// 否则,就需要交换
if (l<r) {
// 将右指针指向的元素值赋给左指针指向的元素值
// 此时arr[r]又可以存其他新的内容了
arr[l] = arr[r];
// 左指针已经填值,因此需要l++
l ++;
}
// 再将左指针向右移动,直到遇到一个比基准值大的元素
while (l<r && arr[l]<pivot) {
l ++;
}
// 同上,下同
if (l<r) {
arr[r] = arr[l];
r --;
}
}
// 此时l=r,说明左右指向了同一个位置
// 而这个位置应该放的是基准值,且一趟排序完成
arr[l] = pivot;
// 对基准值左边部分再进行递归排序
quickSort(arr, left, l-1);
// 对基准值右边部分再进行递归排序
// 由于此时l=r,所以r+1=l+1没影响
quickSort(arr, r+1, right);
}
}
/**
* 合并排序部分
* @param arr 原始数组
* @param tempArr 临时数组
* @param left 当前分组的左边位置序号
* @param right 当前分组的右位置边序号
*/
public void merge(int[] arr, int[] tempArr, int left, int right) {
// 大于1个元素,还可继续划分
if (left < right) {
// 中间位置
int mid = (left+right)/2;
// 左半部分递归划分
merge(arr, tempArr, left, mid);
// 右半部分递归划分
merge(arr, tempArr, mid+1, right);
// 到这里,说明已经划分完,开始向上合并
// 指向左边组序列的第一个
int l = left;
// 指向右边组序列的第一个
int r = mid+1;
// 临时数组的下标,这里的临时数组是存排序后的元素,排完后再复制到原数组中
int tempIndex = left;
// 循环比较,直至左边组或右边组没有剩余元素了才停止
while (l<=mid && r<=right) {
// 可以想象最简单的情况,倒数第二层,有两个元素,需要对这两个元素排序
// 如果左边组的一个元素 < 右边组的一个元素,就将小的那个先放到临时数组中。放完后,下标+1指向下一个元素
if(arr[l]<arr[r]) {
tempArr[tempIndex++] = arr[l++];
}else {
tempArr[tempIndex++] = arr[r++];
}
}
// 可能左边组还有剩余元素,将剩余元素添加到临时数组最后
while (l<=mid) {
tempArr[tempIndex++] = arr[l++];
}
// 可能右边组还有剩余元素,将剩余元素添加到临时数组最后。这里与上面左边剩余的情况不会同时成立
while (r<=right) {
tempArr[tempIndex++] = arr[r++];
}
// 最后将排完顺序的临时数组中的元素复制到原数组中
while (left<=right) {
arr[left] = tempArr[left];
left++;
}
}
// 否则,说明已经划分到最小单元,即一个元素
else {
return;
}
}
public void mergeSort(int[] arr) {
// 开辟一个临时数组
int[] tempArr = new int[arr.length];
// 开始归并排序
merge(arr, tempArr, 0, arr.length-1);
}
public void shellSort(int[] arr) {
for (int inc = arr.length/2; inc > 0; inc/=2) {
for (int i = inc; i < arr.length; i++) {
int key = arr[i];
int j;
for (j = i; j>=inc&&key<arr[j-inc] ; j-=inc) {
arr[j]=arr[j-inc];
}
arr[j]=key;
}
}
}
void heapify(int[] arr, int n, int i) {
// 记录最大值的节点的下标
int largest = i;
// 第i个节点的左子节点的下标:i*2+1
int lson = i*2+1;
// 第i个节点的右子节点的下标:i*2+2
int rson = i*2+2;
// 先比较根节点与左子节点的大小
// 如果左子节点的值更大,就记录左子节点的下标
if (lson<n && arr[lson]>arr[largest]) {
largest = lson;
}
// 再比较根节点(或左子节点,如果上面的if成立的话)与右子节点的大小
// 如果右子节点的值更大,就记录右子节点的下标
if (rson<n && arr[rson]>arr[largest]) {
largest = rson;
}
// 若不相等,则说明largest有变动过,即左或右子节点比根节点大了
if (largest != i) {
// 交换两者的值,把更大的值放到根节点上
int temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
// 递归执行堆维护,因为可能本次调整完后,影响了后面的堆性质,如:
// 3 4
// / \ / \
// 4 1 => 3 1
// / \ / \
// 5 2 5 2
// 3跟4换完后,3跟5也需要换
heapify(arr, n, largest);
}
}
/**
* 大顶堆,堆排序
* @param arr 待排序的数组
*/
public void heapSort(int[] arr) {
int n = arr.length;
// 1.建堆
// 第i个节点的根节点的下标:(i-1)/2
// 最后一个节点的根节点的下标:((n-1)-1)/2 = n/2-1
// 从最后一个根节点到0号根节点依次循环
for (int i = n/2-1; i >= 0; i--) {
// 从下往上维护堆,递归次数少,效率高
heapify(arr, n, i);
}
// 2.排序
// 将最大放到最后
// 由于大顶堆,所以最大值总是在0号节点上
// 从最后一个节点到0号节点依次循环
for (int i = n-1; i > 0; i--) {
// 交换两者的值,把最大值放到后面的节点上
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 交换完成后,对剩余的节点继续执行堆维护
// i: 由于每次都把最大值往后面放,所以这个i可以限制heapify不会影响到后面已排完序的节点
// 0: 从上往下维护堆,之前已经建完堆,这次可能只需要微调
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] arr = new int[]{5,9,1,4,54,6,77,54,3,9,5,66,2,6,34};//,54,3,9,5,66,2,6,34
System.out.println(Arrays.toString(arr));
// new Main().bulbSort(arr);
// new Main().selectionSort(arr);
// new Main().insertSort(arr);
new Main().quickSort(arr, 0, arr.length-1);
// new Main().mergeSort(arr);
// new Main().shellSort(arr);
// new Main().heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}