前言
数据结构和算法是写代码的基础。
基本功非常重要,所谓根基深度决定成长高度。曾经没吃好的饭,总有一天要回来吃的。这段时间项目不忙,回来吃饭,决定花一段时间捋一捋数据结构和算法的基础知识。
当然,能捋多少捋多少吧,这些知识的深度,也不是朝夕之间就能有所成的,本身就是一件须要潜心花费大量时间来学习巩固的东西。
夯实基础。越坚实越好。
正文
这篇博客简要总结了七个算法:冒泡排序。选择排序,插入排序,希尔排序,高速排序。归并排序和堆排序。本文全部的描写叙述都是依据自己的理解手打的,为的是方便读懂。演示样例代码能够实现算法,可是不敢保证就是最优的。如描写叙述内容有误。请指正。
好了開始吧..
1.冒泡排序
从数组的一端開始两两比較,依次将当前最值移动到数组还有一端端的排序方法。经实測。在这几个算法中速度是最慢的。
代码:
/** * 冒泡排序(由小到大) * * @param array * @return */ private static void bubbleSequence(int[] array) { if (null != array) { long ts = System.currentTimeMillis(); int length = array.length; for (int i = 0; i < length; i++) { for (int j = 0; j < length - 1 - i; j++) { if (array[j] > array[j + 1]) exchange(array, j, j + 1); } } long te = System.currentTimeMillis(); System.out.println("冒泡排序 time cost(ms):" + (te - ts)); } }2.选择排序
从数组的一端開始选取元素依次和其它全部元素对照,将最值依次交换到目标位置的排序方法。
代码:
/** * 选择排序(由小到大) * * @param array * @return */ private static void selectSequence(int[] array) { if (null != array) { long ts = System.currentTimeMillis(); int length = array.length; for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (array[j] < array[i]) exchange(array, j, i); } } long te = System.currentTimeMillis(); System.out.println("选择排序 time cost(ms):" + (te - ts)); } }
3.插入排序
把数组中的无序序列元素依次插入到有序序列中的排序方法。对于部分有序序列效率非常高。假设是全然无序序列,则初始有序序列长度为1.
代码:
/** * 插入排序 由小到大 * * @param array * @return */ private static void insertSequence(int[] array) { long ts = System.currentTimeMillis(); if (null != array) { int length = array.length; int temp = 0; // 開始插入排序,第i位依次在前i-1位中找位置 for (int i = 1; i < length; i++) { if (array[i] > array[i - 1]) {// 被比較值比前面都大 continue; } for (int j = 0; j < i - 1; j++) {// 前i位依次对照 if (array[i] < array[j]) { temp = array[i]; for (int k = i; k > j; k--) { array[k] = array[k - 1];// 被插入位置之后的元素依次后挪 } array[j] = temp;// 插入值 break; } } } long te = System.currentTimeMillis(); System.out.println("插入排序 time cost(ms):" + (te - ts)); } }
4.希尔排序
相比而言。前三种都是比較基础的排序方法,easy理解。
从这里開始,要费点脑子了。
希尔排序用到了基础排序方法中的插入排序,它的基本思想是:将数组依照一定的步长分成若干个子数组。(通俗的举个样例,就像让一排人报数,循环报1、2、3,报完过后喊1的人为一组,喊2的人为一组,喊3的人为一组。这一队人就被分成了三个小组。)然后对子数组进行插入排序,使之有序。然后缩小步长,继续分组,排序。
等到步长为1时。排序完毕。经实測希尔排序的效率是非常高的,比前面三种算法速度快十几到几十倍不等。
代码:
/** * 希尔排序 * * @param array * @return */ private static void shellSequence(int[] array) { if (null != array) { long ts = System.currentTimeMillis(); int length = array.length; int stepLength = 1;// 步长 // 计算初始步长 while (stepLength < length / 3) { stepLength = stepLength * 3 + 1; } while (stepLength >= 1) { // 使间隔为h的数组变为有序 for (int i = 0; i < stepLength; i++) // 直接插入排序 { for (int j = i + stepLength; j < length; j += stepLength) if (array[j] < array[j - stepLength]) { int temp = array[j]; int k = j - stepLength; while (k >= 0 && array[k] > temp) { array[k + stepLength] = array[k]; k -= stepLength; } array[k + stepLength] = temp; } } stepLength /= 3;// 步长缩短 } long te = System.currentTimeMillis(); System.out.println("希尔排序 time cost(ms):" + (te - ts)); } }
5.归并排序
归并排序依赖归并操作。即将两个已经排序的序列合并成一个序列的操作,归并排序的过程是:将一个数组拆分成两个子数组,再对子数组进行拆分......直到最后子数组的长度为1,然后子数组按顺序合并,两两合并,两两合并,直到恢复到原数组长度,排序完毕。有一个生动的动图:
代码递归实现:
/** * 归并排序 * * 先将数组拆分为子序列,递归进行,直至分为全部子序列长度都为1。然后将两两子序列合并排序,合并完毕后,排序完毕. * * @param array * 待排序数组 * @param result * 作为挪动空间的辅助数组 * @return */ private static void mergeSequence(int[] array, int result[], int start, int end) { // 參考维基百科的动图。先拆再合。递归执行 if (start >= end) return; if (null != array) { int length = end - start; int middle = (length >> 1) + start; int start1 = start, end1 = middle; int start2 = middle + 1, end2 = end; mergeSequence(array, result, start1, end1); mergeSequence(array, result, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) // 挨个比較值。合并排序 result[k++] = array[start1] < array[start2] ?6.高速排序array[start1++] : array[start2++]; while (start1 <= end1) // 合并1的尾巴 result[k++] = array[start1++]; while (start2 <= end2) // 合并2的尾巴 result[k++] = array[start2++]; for (k = start; k <= end; k++)// 合并后的值赋回原数组 array[k] = result[k]; } }
高速排序的过程是,1.选一个元素作为基准值,将大于基准值的元素放到一边。小于基准值的元素放到还有一边。形成左右两个子序列。然后对子序列继续进行这样的操作,直到子序列长度为1,排序完毕。
代码:
/** * 高速排序 * 依照某个基准值,将数组分为大于该值和小于该值的两个子序列。然后递归的对子序列继续按此方法排序,直到终于子序列长度为1时,排序完毕. * 小规模实验測得,排序效率并不稳定。时快时慢,与详细数组有关. * @param array 待排序数组 * @param start * @param end */ private static void quickSequence(int[] array,int start, int end) { if (start >= end) return; int mid = array[end];//将最后一位元素作为基准值 int left = start, right = end - 1; //设定:左边序列小于基准值。右边序列大于基准值 //从左右两边向中间分别搜索小于和大于基准值的元素。将两边不符合条件的元素相互交换 while (left < right) { while (array[left] < mid && left < right) left++; while (array[right] >= mid && left < right) right--; exchange(array,left, right); } //搜索完毕后。假设左边的元素还大于基准值,则将其与基准值交换。这样的情况一股出如今基准值恰好选成了序列中的最小值 if (array[left] >= array[end]) exchange(array,left, end); else left++; //递归操作左边序列 quickSequence(array,start, left - 1); //递归操作右边序列 quickSequence(array,left + 1, end); }
7.堆排序
i结点的左右子结点下标分别为
2*i+1和2*i+2。package com.test; /** * 堆排序 * * @author Administrator * */ public class HeapSequence { /** * 整理堆 (整理为大顶堆) * * @param array */ public void createHeap(int[] array) { if (null != array) { int startPst = getFatherPosition(array.length - 1); for (int i = startPst; i >= 0; i--) { sortNode(array, i, array.length); } } } /** * 排序 * * @param array */ public void sortHeap(int[] array) { if (null != array) { for (int i = array.length - 1; i > 0; i--) { exchange(array, 0, i); sortNode(array, 0, i); } } } public void sort(int[] array) { createHeap(array); sortHeap(array); } /** * 整理单个节点的堆结构 * * @param array * 目标数组 * @param nodePosition * 节点位置 */ private void sortNode(int[] array, int nodePosition, int heapSize) { int leftChildPst = getLeftChildPosition(nodePosition); int rightChildPst = getRightChildPosition(nodePosition); int largestPosition = nodePosition; if (leftChildPst < heapSize && array[largestPosition] < array[leftChildPst]) { largestPosition = leftChildPst; } if (rightChildPst < heapSize && array[largestPosition] < array[rightChildPst]) { largestPosition = rightChildPst; } // 子节点值有变化,继续整理子节点 if (largestPosition != nodePosition) { exchange(array, largestPosition, nodePosition); sortNode(array, largestPosition, heapSize); } } /** * 父节点位置 * * @param currPst * @return */ public int getFatherPosition(int currPst) { return (currPst - 1) / 2; } /** * 左边子节点位置 * * @param currPst * @return */ public int getLeftChildPosition(int currPst) { return currPst * 2 + 1; } /** * 右边子节点位置 * * @param currPst * @return */ public int getRightChildPosition(int currPst) { return currPst * 2 + 2; } /** * 交换数组中两个位置的值 * * @param a * 数组 * @param x * 位置1 * @param y位置2 */ private static void exchange(int[] a, int x, int y) { int temp = 0; temp = a[x]; a[x] = a[y]; a[y] = temp; } }