算法分类
算法复杂度
1.冒泡排序（稳定）
1.工作原理
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
2.算法原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
3.示例
4.代码实现
- 基本实现
public class BubbleSort {
// a：数组，n：待排序的元素个数
void bubble(int[] a, int n) {
int i;
int temp;
for (i = 0; i < n - 1; i++) {
if (a[i + 1] < a[i]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
void bubbleSort(int[] a) {
int i;
int aLength = a.length;
for (i = aLength; i > 1; i--) {
bubble(a, i);
}
}
}
- 改进
public class BubbleSortImprove {
// 判断是否变换元素位置,即元素是否已经有序
// a：数组，n：待排序的元素个数
boolean bubbleImprove(int[] a, int n) {
int i;
int temp;
boolean change = false;
for (i = 0; i < n - 1; i++) {
if (a[i + 1] < a[i]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
change = true;
}
}
return change;
}
void bubbleSortImprove(int[] a) {
int i;
int aLength = a.length;
boolean change = true;
for (i = aLength; i > 1 && change; i--) {
change = bubbleImprove(a, i);
}
}
}
2.简单选择排序（不稳定）
1.工作原理
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
2.算法原理
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
3.示例
4.代码实现
public class SelectSort {
// a：数组，n：未排序起始下标位置
int findMinIndex(int[] a, int n) {
int i;
int minIndex = n;
int min = a[n];
for (i = n + 1; i < a.length; i++) {
if (min > a[i]) {
min = a[i];
minIndex = i;
}
}
return minIndex;
}
void selectSort(int[] a) {
int i = 0;
while (i < a.length - 1) {
int minIndex = findMinIndex(a, i);
// 将最小值变换至已排序元素末尾
if (minIndex != i) {
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
i++;
}
}
}
3.直接插入排序（稳定）
1.工作原理
每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
2.算法原理
- 从序列第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，设为待插入元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。
- 重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素
- 重复2，3步骤，完成排序
3.示例
4.代码实现
public class InsertSort {
// a：数组，n：要进行插入的元素的下标
void insert(int[] a, int n) {
int key = a[n];
int i = n;
while (a[i - 1] > key) {
a[i] = a[i - 1];
i--;
if (i == 0) {
break;
}
}
a[i] = key;
}
void insertSort(int[] a) {
int i = 1;
while (i < a.length) {
insert(a, i);
i++;
}
}
}
4.希尔排序【缩小增量排序】（不稳定）
基本有序：小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。
例：{2,1,3,6,4,7,5,8,9}是，{1,5,9,3,7,8,2,4,6}不是
1.工作原理
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
2.算法原理
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个来处理，表长度即为整个序列的长度。
3.示例
4.代码实现
public class ShellSort {
// a：数组，increment：增量
void shell(int[] a, int increment) {
int i;
int ii;
int j = 0;
int key;
int aLength = a.length;
// 按照增量分组个数的遍历
while (j < increment) {
// 每个组进行插入排序
for (i = j + increment; i < aLength; i += increment) {
key = a[i];
ii = i; //保持循环条件i不变
while (a[i - increment] > key) {
a[i] = a[i - increment];
i -= increment;
if (i < increment) {
break;
}
}
a[i] = key;
i = ii;
}
j++;
}
}
void shellSort(int[] a) {
int aLength = a.length;
int increment = aLength / 3 + 1;
int statue = 0; //控制当增量 increment=1 时进行最后一字排序
do {
shell(a, increment);
increment = increment / 3 + 1;
if (increment == 1) {
statue++;
}
} while (statue < 2);
}
}
5.堆排序（不稳定）
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
1.工作原理
指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2.算法原理
- 将待排序的序列(R1,R2….Rn)构造成为一个大顶堆【小顶堆】
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]【R[1,2…n-1]>=R[n]】；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
- 重复以上步骤直到有序区的元素个数为n-1，则整个排序过程完成。
3.示例
4.代码实现
public class HeapSort {
/**
* 完全二叉树性质（自上而下，从左至右，由1开始编码）： 1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1，择其双亲是结点⌊i/2⌋.
* 2.如果2i>n，则结点i无左孩子(结点i为叶子节点)；否则其左孩子是结点2i。 2.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。
**/
// a：待排序数组，n：未排序的长度
void heap(int[] a, int n) {
int i;
for (i = n / 2; i > 0; i--) {
int father = a[i - 1];
int maxChild = a[2 * i - 1];
int maxChildIndex = 2 * i - 1;
if (2 * i + 1 <= n) {
if (a[2 * i - 1] < a[2 * i]) {
maxChild = a[2 * i];
maxChildIndex = 2 * i;
}
}
if (father < maxChild) {
a[i - 1] = maxChild;
a[maxChildIndex] = father;
}
}
}
void heapSort(int[] a) {
int aLength = a.length;
while(aLength>1) {
heap(a, aLength);
// 将最大值与末尾元素交换
{
int temp = a[0];
a[0] = a[aLength-1];
a[aLength-1] = temp;
}
// 需排序长度减一
aLength--;
}
}
}
6.归并排序（稳定）
1.工作原理
建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2.算法原理
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
3.示例
4.代码实现
public class MergeSort {
// a：数组,l：归并左侧起始下标,m：l和r的分界(归并右侧起始下标),r：归并右侧末尾下标
void merge(int[] a, int l, int m, int r) {
int leftSize = m - l;
int rightSize = r - m + 1;
int[] left = new int[leftSize];
int[] right = new int[rightSize];
int i, j, k;
for (i = l; i < m; i++) {
left[i - l] = a[i];
}
for (i = m; i <= r; i++) {
right[i - m] = a[i];
}
// 左右进行归并排序
i = 0;
j = 0;
k = l;
while (i < leftSize && j < rightSize) {
if (left[i] < right[j]) {
a[k] = left[i];
k++;
i++;
} else {
a[k] = right[j];
k++;
j++;
}
}
while (i < leftSize) {
a[k] = left[i];
k++;
i++;
}
while (j < rightSize) {
a[k] = right[j];
k++;
j++;
}
}
// a:数组,l:排序起始位置,r:排序末尾位置
void mergeSort(int[] a,int l, int r) {
if(l == r) {
return;
}
int m = (l+r)/2;
// 左侧进行归并
mergeSort(a, l, m);
// 右侧进行归并
mergeSort(a, m+1, r);
merge(a, l, m+1, r);
}
}
7.快速排序（不稳定）
1.工作原理
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2.算法原理
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列重复1、2步骤。
使用分治法来把一个串（list）分为两个子串（sub-lists）:
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]的值赋给A[i]；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]的值赋给A[j]；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
3.示例
4.代码实现
public class QuickSort {
// 返回前基准所在下标
// a:数组,low:需要排序的起始下标,high:需要排序的末尾下标
int quick(int[] a, int low, int high) {
int pivotIndex = low;
int pivot = a[low];
while (low < high) {
// 自后向前搜索一个较小值
while (low < high) {
if (a[high] < pivot) {
int temp = a[high];
a[high] = pivot;
a[low] = temp;
pivotIndex = high;
low++;
break;
}
high--;
}
// 自前向后搜索一个较大值
while (low < high) {
if (a[low] > pivot) {
int temp = a[low];
a[low] = pivot;
a[high] = temp;
pivotIndex = low;
high--;
break;
}
low++;
}
}
return pivotIndex;
}
void quickSort(int[] a, int low, int high) {
int pivotIndex = quick(a, low, high);
// 小于基准部分（基准左侧）进行排序
if (pivotIndex > low) {
quickSort(a, low, pivotIndex - 1);
}
// 大于基准部分（基准右侧）进行排序
if (pivotIndex < high) {
quickSort(a, pivotIndex + 1, high);
}
}
}
7.基数排序（稳定）
1.工作原理
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
2.算法原理
- 取得数组中的最大数，并取得位数；
- 原始数组从最低位开始取每个位组成radix数组,然后赋值给原数组；
- 重复步骤2，知道最大位数，排序结束。
3.示例
4.代码实现
public class RadixSort {
// a：数组，n：元素个十百千位
void radix(int[] a, int n) {
// b：存储相对应位的数组的值
int[][] b = new int[10][a.length];
// c：存储相对应位的元素个数
int[] c = new int[10];
int i, key;
for (i = 0; i < a.length; i++) {
key = (a[i] / (int) Math.pow(10, n - 1)) % 10;
b[key][c[key]] = a[i];
c[key]++;
}
// 将排序后的数组赋予原数组
int j = 0;
for (int k1 = 0; k1 < b.length; k1++) {
for (int k2 = 0; k2 < c[k1]; k2++) {
a[j++] = b[k1][k2];
}
}
}
void radixSort(int[] a) {
int max = a[0];
int i = 1;
while (i < a.length) {
if (max < a[i]) {
max = a[i];
}
i++;
}
// j：a数组中最大值的位数
int j = 1;
for (j = 0; max > 0; j++) {
max /= 10;
}
int k = 1;
while (k <= j) {
radix(a, k);
k++;
}
}
}
```
网友评论