石景山网站建设的大公司,丹徒网站建设方案,昆明网页建站平台,wordpress 静止ip访问插入排序
package learn;import java.util.Arrays;/** 每次都将当前元素插入到左侧已经排序的数组中#xff0c;使得插入之后左侧数组依然有序。* 速度优于选择排序*/
public class InsertSort {public static void insertSort(int[] a) {int n a.length;for (int i 1; i import java.util.Arrays;/** 每次都将当前元素插入到左侧已经排序的数组中使得插入之后左侧数组依然有序。* 速度优于选择排序*/
public class InsertSort {public static void insertSort(int[] a) {int n a.length;for (int i 1; i n; i) {// 为了将当前元素插入到已经排序的数组中需要从后往前遍历for (int j i; j 0 ; j--) {if (a[j] a[j - 1]) {int temp a[j];a[j] a[j - 1];a[j - 1] temp;} else {continue;}}}}public static void main(String[] args) {
// int[] s {4, 6, 1, 2, 3, 0};int[] s {9,7,1,-8,36,-18,100};System.out.println(Arrays.toString(s));insertSort(s);System.out.println(Arrays.toString(s));}
}
堆
package sort;/*** 【大顶堆】* 堆中某个节点的值总是大于等于其子节点的值并且堆是一颗完全二叉树。** 堆可以用数组来表示这是因为堆是完全二叉树而完全二叉树很容易就存储在数组中。* 位置 k 的节点的父节点位置为 k/2而它的两个子节点的位置分别为 2k 和 2k1。* param T*/
public class duiT extends ComparableT {private T[] heap;private int N 0;public dui(int maxN) {this.heap (T[]) new Comparable[maxN 1];}public boolean isEmpty() {return N 0;}public int size() {return N;}private boolean less(int i, int j) {return heap[i].compareTo(heap[j]) 0;}private void swap(int i, int j) {T t heap[i];heap[i] heap[j];heap[j] t;}// 上浮把大元素向上排private void swim(int k) {// k 的父节点 k/2 更小的时候需要对 k 做上浮操作while (k 1 less(k / 2, k)) {swap(k / 2, k);// 交换k k / 2;// 更改当前 k 的位置}}// 下沉把小元素往下排private void sink(int k) {// k 的子节点分别是 k*2 与 k*21while (2 * k N) {int j 2 * k;if (j N less(j, j 1))// 左子节点要小于右子节点j;// 若父节点 左子节点 就表示if (!less(k, j))break;// 父节点 左子节点就需要交换swap(k, j);k j;}}// 插入元素:将新元素放到数组末尾然后上浮到合适的位置。public void insert(T v) {heap[N] v;swim(N);}// 删除最大元素:// 从数组顶端删除最大的元素并将数组的最后一个元素放到顶端并让这个元素下沉到合适的位置。public T delMax() {T max heap[1];swap(1, N--);heap[N 1] null;sink(1);return max;}
}
堆排序
package sort;import java.util.Arrays;/*** 把最大元素和当前堆中数组的最后一个元素交换位置并且不删除它* 那么就可以得到一个从尾到头的递减序列从正向来看就是一个递增序列* 这就是堆排序。*/
public class HeapSort {public static void heapSort(int[] a) {int N a.length - 1;// 从右至左进行下沉操作for (int k N / 2; k 1; k--) {sink(a, k, N);}while (N 1) {swap(a, 1, N--);sink(a, 1, N);}}// 下沉private static void sink(int[] a, int k, int N) {while (2 * k N) {int j 2 * k;if (j N less(a[j], a[j 1]))j;if (!less(a[k], a[j]))break;swap(a, k, j);k j;}}private static boolean less(Comparable v, Comparable w) {// 若 v 小于 w 则返回负数return v.compareTo(w) 0;}private static void swap(int[] a, int i, int j) {int t a[i];a[i] a[j];a[j] t;}public static void main(String[] args) {int[] a {1, 9, 2, 8, 3, 6, 7};System.out.println(Arrays.toString(a));heapSort(a);System.out.println(Arrays.toString(a));}}
快速排序
package sort;import java.util.Arrays;/*** 使用最广泛的排序算法* 原理上是一种分治算法将一个数组分为两部分对这两部分独立的排序然后整体有序* 与归并排序的区别* 1归并排序虽然也是把数组分为两部分但是归并排序需要在部分有序后再做一次排序来让整体有序* 但是快速排序是部分有序了整体自然就有序了无需对整体再一次排序。* 2归并排序的数组切分是平分但是快速排序的数组切分是根据数组内容由函数产生的*/
public class QuickSort {public static void quickSort(int[] a, int start, int end) {if (end start) {return;}// j 是中分点parttion算法是关键int j partition(a, start, end);quickSort(a, start, j - 1);// 针对左边排序quickSort(a, j 1, end); // 针对右边排序}private static boolean less(Comparable v, Comparable w) {// 若 v 小于 w 则返回负数return v.compareTo(w) 0;}private static void exch(int[] a, int i, int j) {int t a[i];a[i] a[j];a[j] t;}/*这段代码按照a[start]的值v进行切分。当指针i和j相遇时主循环退出。在循环中a[i]小于v时我们增大ia[j]大于v时我们减小j然后交换a[i]和a[j]来保证i左侧的元素都不大于v, j右侧的元素都不小于V。当指针相遇时交换a[start]和a[j]切分结束(这样切分值就留在a[j]中了)。*/private static int partition(int[] a, int start, int end) {// i、j 两根指针分别从左右开始寻找第一个大于 v 的与第一个小于 v 的值int i start;int j end 1;int v a[start];while (true) {// 找到第一个大于 v 的值与 iwhile (less(a[i], v)) {if (i end) {break;}}// 找到第一个小于 v 的值与 jwhile (less(v, a[--j])) {if (j start) {break;}}// i、j 指针相交后if (i j) {break;}// 交换 i、j 处的值确保 i 左边的都不大于 vj 右边的都不小于 vexch(a, i, j);}exch(a, start, j);// 将 V a[j]放入正确的位置return j;}public static void main(String[] args) {
// int[] a {12, 6, 9, 3, 78, 3, 3, 4};int[] a {9, 7, 1, -8, -1, -18, 100};System.out.println(Arrays.toString(a));quickSort(a, 0, a.length - 1);System.out.println(Arrays.toString(a));}
}
冒泡排序
package sort;public class BubbleSort {public static void bubbleSort(int[] a) {// 冒泡排序的最大的特点就是顺序是从右往前逐渐有序的// 所以随着排序的逐渐执行右边的越来越有序但是每一次比较缺还在比较已经有序的部分// 因此需要排除遍历这部分有序的数据也就是内循环只遍历到右边有序数据的前面就行了不能再往后遍历了int sortedBorder a.length - 1;// 这个 lastSwapIndex 肯定是从大数开始减少的代表着右边的数据在排序int lastSwapIndex 0;for (int i 0; i a.length; i) {boolean isSorted true;for (int j 0; j sortedBorder; j) {if (a[j] a[j 1]) {a[j] ^ a[j 1];a[j 1] ^ a[j];a[j] ^ a[j 1];isSorted false;lastSwapIndex j;}}// 内循环遍历结束代表着右边已经部分有序了最后一次排序的 j 就是有序无序的边界sortedBorder lastSwapIndex;if (isSorted) {break;}}}public static void main(String[] args) {int[] arr {6, 3, 8, 2, 9, 1, 0, 5, 4, 7, -1};
// int[] arr {6, 3, 8, 12, 19, 110};
// int[] arr {0, 3, 8, 12, 19, 110};System.out.println(排序前数组为);for (int num : arr) {System.out.print(num );}bubbleSort(arr);System.out.println();System.out.println(排序后的数组为);for (int num : arr) {System.out.print(num );}}
}
希尔排序
package sort;import java.util.Arrays;
/*
希尔排序是基于插入排序的一种快速排序算法
插入排序的缺点对于大规模的乱序数组排序速度慢
希尔排序简单的改变了插入排序交换不相邻的元素以对数组的局部进行排序
并最终用插入排序将局部有序的数组排序希尔排序对于大型数组排序效率很高不需要额外的内存空间*/
public class ShellSort {public static void shellSort(int[] a) {int n a.length;// 设置增量增量的取法有很多这里是推荐取法// 插入排序的增量是1,属于相邻元素比较现在换成不相邻元素比较int h 1;while (h n / 3) {h 3 * h 1;}// 增量最小为 1 也就是相邻的两个元素比较while (h 1) {// 对相聚 h 的两个元素使用插入排序for (int i h; i n; i) {for (int j i; j h less(a[j], a[j-h]); j - h) {exch(a, j, j-h);}}// 排序结束后缩小增量继续排序h / 3;}}private static void exch(int[] a, int i, int j) {int t a[i];a[i] a[j];a[j] t;}private static boolean less(Comparable v, Comparable w) {// 若 v 小于 w 则返回负数return v.compareTo(w) 0;}public static void main(String[] args) {
// int[] s {3, -2, -1};int[] s {9,7,1,-8,-1,-18,100};System.out.println(Arrays.toString(s));shellSort(s);System.out.println(Arrays.toString(s));}
}
选择排序
package sort;import java.util.Arrays;/*** 在数组里面选择最小的放到第一位然后在剩下的数组里面找到最小的放到第二位如此反复直到结束*/
public class SelectSort {public static void selectSort(int[] a) {int n a.length;for (int i 0; i n-1; i) {for (int j i 1; j n; j) {// 要始终保持最小值为当前的 iint minIndex i;boolean exchange true;// 如果 a[j] a[min] 说明需要把 j 设置为最小的if (a[j] a[minIndex]) {minIndex j;} else {exchange false;}// 如果需要交换数据就开始交换if (exchange) {int temp a[i];a[i] a[j];a[j] temp;}}}}public static void main(String[] args) {int[] array {0, 200, -523, 7, 1, -1, -18, 2, 10, -6};System.out.println(Arrays.toString(array));selectSort2(array);System.out.println(Arrays.toString(array));}public static void selectSort2(int[] array) {for (int i 0; i array.length; i) {for (int j i 1; j array.length; j) {// 假设 i 所处位置的元素就是最小的int min i;if (array[j] array[min]) {// 后面的更小就要排序到前面array[i] ^ array[j];array[j] ^ array[i];array[i] ^ array[j];}}}}
}
优先队列排序
package sort;import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;public class Test {private static class Customer {private Integer id;private String name;public Integer getId() {return id;}public void setId(Integer id) {this.id id;}public String getName() {return name;}public void setName(String name) {this.name name;}public Customer(Integer id, String name) {this.id id;this.name name;}public Customer() {}Overridepublic String toString() {return weight id , name name;}}public static void main(String[] args) {// 1.演示优先队列的自然排序QueueInteger naturePriorityQueue new PriorityQueue(10);for (int i 0; i 10; i) {int random (int) (Math.random() * 100000 1);System.out.println(add i value random);naturePriorityQueue.add(random);Integer peek naturePriorityQueue.peek();System.out.println(poll i value peek);System.out.println();}// 2.演示自定义排序QueueCustomer customerPriorityQueue new PriorityQueue(10, idComparator);// 初始化队列大小并指定比较器for (int i 0; i 10; i) {Customer customer new Customer((int) (Math.random() * 6532 1), customer i);System.out.println(add customer is customer.toString());customerPriorityQueue.add(customer);Customer customer1 customerPriorityQueue.peek();System.out.println(peek customer is customer1.toString());System.out.println();}}// 自定义的比较器public static ComparatorCustomer idComparator new ComparatorCustomer() {Overridepublic int compare(Customer o1, Customer o2) {return o1.getId() - o2.getId();}};}
自顶向下的归并实现
package sort;import java.util.Arrays;public class MergeSortUp2Down {/*该方法用来拆解原数组为一个个单一的元素*/public static void mergeSortUp2Down(int[] array, int start, int end) {if (start end)return;int mid (start end) 1; // 把除法换成位运算mergeSortUp2Down(array, start, mid);mergeSortUp2Down(array, mid 1, end);// 拆完后进入比较排序处理阶段merge(array, start, mid, end);}/*每一次进入该方法就代表一个小阶段的归并需要一个临时数组存储排序的数据不是修改原始数据归并完了之后可能还有一部分数据本来有序无需归并把他们加入到临时数组后面到此为止归并才真正的结束现在知道归并时为什么不能修改原始数组了吧最后把归并的结果写回到原始数组中*/private static void merge(int[] array, int start, int mid, int end) {// 归并的特点是两两比对但不是只比对两个数是两组用 i、j 指向这两组元素的第一个int i start;int j mid 1;int index 0;// 存储新排序的数据int[] tmp new int[end - start 1];while (i mid j end) { // 前面的一组不能越 mid 界后面一组不可以越 end 界if (array[j] array[i]) {tmp[index] array[j];} else {tmp[index] array[i];}}while (i mid) {tmp[index] array[i];}while (j end) {tmp[index] array[j];}// 把现在的有序数据写回到原始数组里面for (index 0; index tmp.length; index) {array[start index] tmp[index];}}public static void main(String[] args) {int[] a {6, 3, 7, 2, 2, 3, 4, 9, 1, -1};mergeSortUp2Down(a, 0, a.length - 1);System.out.println(Arrays.toString(a));}
}
