从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的 *** 作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换 *** 作。
步骤具体步骤：
-
首先在未排序序列中找到最小（大）元素，记录下标minIndex，与数组第一个值进行交换。
-
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
-
重复第二步，直到所有元素均排序完毕。
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
SelectSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public class void SelectSort(int[] arr){
for (int i; i
冒泡排序
介绍
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
动图
实现
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
bubbleSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public void bubbleSort(int[] arr){
for (int i=1; i arr[j+1]){
swap(arr, j, j+1);
flag = false;
}
}
if (flag) break;
}
}
public class swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
插入排序
直接插入排序
介绍
直接插入排序是插入排序算法中的一种，采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
步骤
- 从第一个元素开始，该元素可以认为已经排好序。
- 取出下一个新元素，然后把这个新元素在已经排好序的元素序列中从后往前扫描进行比较。
- 如果该元素(已排序) 大于新元素，则进行交换顺序。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该已排序的元素的索引位置后面。
- 重复步骤2~5
动图
实现
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
bubbleSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public void bubbleSort(int[] arr){
for (int i=1; i0; j--){
// 从后往前遍历，当前元素为待排序数，判断它和前一个的大小，前一个数比它大，则进行交换
if(arr[j] < arr[j-1])
swap(arr, j, j-1);
}
}
}
}
public class swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
折半插入排序
折半插入排序法，又称二分插入排序法，是直接插入排序法的改良版，也需要执行i-1趟插入，不同之处在于，第i趟插入，先找出第i+1个元素应该插入的的位置，假定前i个数据是已经处于有序状态。
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
bubbleSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public void bubbleSort(int[] arr){
for (int i=1; i temp)
right = mid - 1;
else
left = mid + 1;
}
for (j=i; j > left; j--){
arr[j] = arr[j-1];
}
}
}
}
}
链表插入排序
表插入排序，即使用链表的存储结构对数据进行插入排序。在对记录按照其关键字进行排序的过程中，不需要移动记录的存储位置，只需要更改结点间指针的指向。
插入排序的主要的思想在于：
- 利用一个前继节点的概念去寻找当前值比前一个值大的节点
- 对前面插入的内容进行排序，然后我们每次从第一个节点开始遍历这个链表进行比较然后插入。
public class linkedInsertSort {
static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public static ListNode insertionSortList(ListNode head){
if(head==null||head.next==null) return head;
ListNode pre = head;//pre指向已经有序的节点的尾部
ListNode cur = head.next;//cur指向待排序的节点首部
// 此时pre对象相当与head对象的引用，而并不是将head对象的值单纯的传递给pre对象。即：pre对象的 *** 作将直接改变head对象。如pre.add(“3”);结果head中也包含了“3”；
// 创建辅助节点是因为要对源节点进行修改
ListNode tmp = new ListNode(-1); // 辅助节点
tmp.next = head; // tmp.next记录返回链表的头部
while(cur!=null){
if(cur.val < pre.val){
//先把cur节点从当前链表中删除，然后再把cur节点插入到合适位置
pre.next = cur.next;
// pre里面不存在cur了，修改了head
// 从新链表头部开始找到要插入的节点位置
ListNode l1 = tmp;
ListNode l2 = tmp.next;
while(cur.val > l2.val){
l1 = l2;
l2 = l2.next
}
// 断开节点，插入cur
l1.next = cur;
cur.next = l2;
// 重写将cur指向待排序链表的首部位置
cur = pre.next;
}else {
// 当前节点大于前一个节点，则不排序，指针向后移动
pre = cur;
cur = cur.next;
}
}
return tmp.next;
}
}
希尔排序
希尔排序(缩小增量法) 属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h = 3 * h +1
反过来程序需要反向计算h序列，应该使用
h=(h-1)/3
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
动图
实现
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
ShellSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public void ShellSort(int[] arr){
int N = arr.length;
int h = 1;
// 计算出最大的h值
while(h < N/3){
h = 3 * h + 1;
}
while(h >= 1){
// 4. 从 arr[h] 开始往后遍历，将遍历到的数据与其小组进行插入排序
for(int i = h; i = 0 && arr[j - h] > tmp){
// 向后移动h位置
arr[j] = arr[j - h];
// 进行向前移动h位置
j -= h;
}
// 进行插入
arr[j] = tmp;
}
// 计算出下一个h值
h = (h - 1) / 3;
}
}
}
归并排序
归并排序的实现是使用了一种分而治之的思想，即将一个数组不断地通过两两分组的方式进行比较大小，最后直到所有元素都被分到一组里，那自然就是整体有序的了。
工作原理：
归并排序就是递归得将原始数组递归对半分隔，直到不能再分(只剩下一个元素)后，开始从最小的数组向上归并排序
-
向上归并排序的时候，需要一个暂存数组用来排序，
-
将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移，
-
直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里，
-
再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。
递归
public class Sort {
public static void main(String[] args){
int[] arr = {1,3,4,2,6,8};
MergeSort(arr);
for(int i:arr) System.out.print(i + " ");
}
public void MergeSort(int[] arr){
// 避免生成大量的临时对象，声明等大数组存储空间
int[] tmp = new int[arr.length];
merge(arr, 1, arr.length, tmp);
}
public static void merge(int[] arr, int low, int high, int[] tmp){
if (low < high){
int mid = (low + high) / 2;
merge(arr, low, mid); //对左边序列进行归并排序
merge(arr, mid + 1, high); //对右边序列进行归并排序
doMerge(arr, low, mid, high, tmp);
}
}
// 注：数组下标0开始，所有取值都-1
//
public static void doMerge(int[] arr, int begin, int mid, int end, int[] tmp) {
int count = 0; // tmp的起始位置
int index = begin;
int position = mid + 1;
while(index <= mid && position <= end) {
if(arr[index] < arr[position]) tmp[count++] = arr[index++];
else tmp[count++] = arr[position++];
}
// 将剩余数组全部放入tmp
while(index <= mid) tmp[count++] = arr[index++];
while(position <= end) tmp[count++] = arr[position++];
// 之前只是把排序的结果存在了tmp临时数据里，现在要把这部分复制到原来的arr数组对应的位置，这样在下一次用到arr的时候才是我们这次排好序的
for (int t = 0; t < count; t++) arr[index + t] = tmp[t];
}
}
自低向上化递归为迭代–不确定
public void MergeSort(int[] arr){
// 避免生成大量的临时对象，声明等大数组存储空间
int[] tmp = new int[arr.length];
merge(arr, 1, arr.length, tmp);
}
public static void merge(int[] arr, int low, int high, int[] tmp){
int size,i;
int n = arr.length;
// size设置每一次分的段的长度，如图中的2个元素为一小段，4个元素为一小段中的2和4
// i设置每一次归并排序的数组下标的范围
for(size = 1, size < n; size+=size ) //让其以2的倍数逐渐增加:2,4,8,16...
{
for(i = 0 ; i < n - size ; i += size + size ) //因为是每次两个小段一合并，所以i的跨度为两个小段的长度
//这里改为i< n - size 确保了后一段的存在，也保证了下标值不会越界
doMerge(arr, i, i+size-1, Math.min(i + size + size - 1, n - 1), tmp);
//这个函数是说将arr数组中的[i,i+size-1],[i+size,i+size+size-1] 这两部分进行合并
// 保证i+size-1和i+size+size-1在数组边界, 这里与n-1取最小值可以保证我们最后一个下标不会越界
}
}
不递归
快速排序非递归的执行过程中，只需要一个堆栈空间，其运行过程如下：
- 对原数组进行一次划分，分别将左边的 Record 和 右边的 Record 入栈 stack。
- 判断 stack 是否为空，若是，直接结束；若不是，将栈顶 Record 取出，进行一次划分。
- 判断左边的 Record 长度（这里指 record.right - record.left + 1）大于 1，将左边的 Record 入栈；同理，右边的 Record。
- 循环步骤 2、3。
public void sort(int[] array) {
int left = 0;
int right = array.length - 1;
if (left < right) {
int pivot = partitionSolution.partition(array, left, right);
if (pivot - 1 >= left) {
stack.push(new Record(left, pivot - 1));
}
if (pivot + 1 <= right) {
stack.push(new Record(pivot + 1, right));
}
while (!stack.isEmpty()) {
Record record = stack.pop();
pivot = partitionSolution.partition(array, record.left, record.right);
if (pivot - 1 >= record.left) {
stack.push(new Record(record.left, pivot - 1));
}
if (pivot + 1 <= record.right) {
stack.push(new Record(pivot + 1, record.right));
}
}
}
链表的归并排序
知识点1：归并排序的整体思想
知识点2：找到一个链表的中间节点的方法
- 直接遍历一遍
- 使用快慢指针，一个走一步，一个走两步，则走两步的到达末尾，走一步的到中间
知识点3：合并两个已排好序的链表为一个新的有序链表
归并排序的基本思想是：找到链表的middle节点，然后递归对前半部分和后半部分分别进行归并排序，最后对两个以排好序的链表进行Merge。归并排序的重点在于：我们要确定递归切分的退出的条件在这里是（head == null || head.next != null）还有就是归并时候：要注意退出的条件
public ListNode MergeSort(ListNode head){
if (head== null || head.next == null) return head;
ListNode mid = getMid(head); // 获取链表中间节点
//把链表从之间拆分为两个链表：head和second两个子链表
ListNode second = mid.next;
mid.next = null;
//对两个子链表分割
ListNode left = mergeSort(head);
ListNode right = mergeSort(second);
// 排序
return merge(right,left);
}
public ListNode merge(ListNode right, ListNode left){
if(left == null){
return right;
}
if(right == null){
return left;
}
//辅助节点，排好序的节点将会链接到dummy后面
ListNode dummy = new ListNode(0);
ListNode tail = dummy; //tail指向最后一个排好序的节点
while(right != null && left != null){
if (right.val < left.val) {
tail.next = right;
right = right.next;
} else {
tail.next = left;
right = left.next;
}
tail = tail.next;
}
// 填充剩余链表
if(right != null) tail.next = right;
else tail.next = left;
return dummy.next;
}
public ListNode getMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
// 最后一个，或者倒数第二个
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
快速排序
Quick sort
基本算法快速排序使用分治的思想，从待排序序列中选取一个记录的关键字为key，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字不大于key，另一部分记录的关键字不小于key，之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序算法的基本步骤为（从小到大）：
- 选择关键字：从待排序序列中，按照某种方式选出一个元素作为 key 作为关键字（也叫基准）。
- 置 key 分割序列：通过某种方式将关键字置于一个特殊的位置，把序列分成两个子序列。此时，在关键字 key 左侧的元素小于或等于 key，右侧的元素大于 key（这个过程称为一趟快速排序）。
- 对分割后的子序列按上述原则进行分割，直到所有子序列为空或者只有一个元素。此时，整个快速排序完成。
挖坑法
public static int[] quickSort(int arr[], int start, int end){
if (start >= end) return;
// 以开始点为
int tmp = arr[begin];
int left = start;
int right = end;
while (left < right){
while(arr[right] >= tmp && right > left) right--;
arr[left] = arr[right];
while(arr[left] <= tmp && right > left) left++;
arr[right] = arr[left];
}
// 将中间基准点，放在中间，之后基准不动
arr[left] = tmp;
quickSort(arr, start, left - 1);
quickSort(arr, left + 1, end);
}
优化快速排序之所以比较快，是因为与冒泡排序相比，每次的交换时跳跃式的，每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。
优化一：当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时使用插排对其优化
优化二：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割
基于切分的快速选择算法快速排序的 partition() 方法，会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j]，且 a[j+1…h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 个元素。
该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+…)，直到找到第 k 个元素，这个和显然小于 2N。
前后分别排序
堆排序堆排序是一种原地排序，没有利用额外的空间。
一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
基本思想：
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
代码1、首先将无需数组构造成一个大根堆（新插入的数据与其父结点比较）
2、固定一个最大值，将剩余的数重新构造成一个大根堆，重复这样的过程
public static void heapSort(int[] arr) {
//1.构建大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr, i, arr.length);
}
//然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, j);//重新对堆进行调整
}
}
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];//先取出当前元素i
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2*i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
k++;
}
if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];//把较大的值，赋给当前节点
i = k;//i 指向k,继续循环比较
} else {
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
排序算法的比较
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。
Java 的排序算法实现Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）