算法 ----排序算法
2019-01-02 本文已影响126人
谷哥得小弟
1、排序算法有哪些？
插入排序： 直接插入排序、希尔排序
选择排序： 简单选择排序、堆排序
交换排序：冒泡排序、快速排序
归并排序：
基数排序：
2、最快的排序算法是哪个？
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
3、冒泡排序
思想：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
冒泡.png
代码实现：
@Test
public void bubbleSortTest() {
int a[] = {3, 1, 2, 6, 4, 2};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(a, a.length);
}
/**
* 冒泡排序
* @param a
* @param n
*/
public void bubbleSort(int a[], int n){
for(int i =0 ; i< n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(a[j] > a[j+1])
{
int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
for(int i =0 ; i< n; i++) {
System.out.print("\t\t"+a[i]);
}
}
输出结果：
冒泡输出.png
冒泡排序优化：
对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。对上述代码优化如下：
@Test
public void bubbleSortTest() {
int a[] = {3, 1, 2, 6, 4, 2,8,3,4,5,66,3,2,1,5,5,3,7};
BubbleSort bubbleSort = new BubbleSort();
bubbleSort.bubbleSort(a, a.length);
}
/**
* 冒泡排序
*
* @param a
* @param n
*/
public void bubbleSort(int a[], int n) {
int pos = 0;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
pos++;
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
if (pos == 0) {
System.out.print("排序好了：第" + (i+1) + "趟");
break;
}
pos = 0;
}
for (int i = 0; i < n; i++) {
System.out.print("\t\t" + a[i]);
}
}
输出如下：
冒泡优化.png
可以看到18组数据外层只排了13次就已经排序完成，优化了代码效率。
4、快速排序
思想：
1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
（a）一趟排序的过程：
快排一趟.png
（b）排序的全过程：
快排全过程.png
代码实现：
@Test
public void quickSort() {
int a[] = {3,1,5,7,2,4,9,6,10,8};
QuickSort quickSort = new QuickSort();
System.out.print("brefore:");
quickSort.print(a, a.length);
quickSort.quickSort(a,0,a.length-1);
System.out.print("after:");
quickSort.print(a, a.length);
}
/**
* 快排
*
* @param a
* @param low
* @param high
*/
public void quickSort(int a[], int low, int high) {
if (low < high) {
int privotLoc = partition(a, low, high); //将表一分为二
quickSort(a, low, privotLoc - 1); //递归对低子表递归排序
quickSort(a, privotLoc + 1, high); //递归对高子表递归排序
}
}
private int partition(int a[], int low, int high) {
int privotKey = a[low]; //基准元素
while (low < high) { //从表的两端交替地向中间扫描
while (low < high && a[high] >= privotKey)
--high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
swap(a,low,high);
while (low < high && a[low] <= privotKey) ++low;
swap(a,low,high);
}
print(a, a.length);
return low;
}
private void swap(int a[], int low, int high) {
int tmp = a[low];
a[low] = a[high];
a[high] = tmp;
}
public void print(int a[], int n) {
for (int j = 0; j < n; j++) {
System.out.print(a[j]+"\t");
}
System.out.print("\n");
}
上面代码中很重要的是
while (low < high) { //从表的两端交替地向中间扫描
while (low < high && a[high] >= privotKey)
--high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
swap(a,low,high);
while (low < high && a[low] <= privotKey) ++low;
swap(a,low,high);
}
对后排依次递减扫描，扫描到后面的小于基线位置数时把其放到基线前面；对前排递增扫描，扫描到前排大于基线位置，停止while，交换当前扫描前段以及后段。最后返回动态的基线最新位置。
输出结果：
快排结果.png
快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。
5、选择排序
思想：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
排序过程：（由于绘图比较麻烦，下面直接用代码控制台输出排序过程了）
select.png
实现代码：
@Test
public void selectSort(){
int a[] = {3,1,5,7,2,4,9,6,10,8};
SelectSort selectSort = new SelectSort();
System.out.print("Select brefore:");
selectSort.print(a, a.length);
selectSort.SelectSort(a,a.length);
System.out.print("Select after:");
selectSort.print(a, a.length);
}
/**
* 选择排序
* 第一趟：从数组中选出最小（或者最大）的一个数与第1个位置的数交换
*
* @param a
* @param n
*/
public void SelectSort(int a[], int n) {
for (int i = 0; i < n; i++) {
int minVaule = a[i]; //一趟预置最小值
int temp;
for (int j = i + 1; j < n; j++) {
if (minVaule > a[j]) {
temp = a[j];
a[j] = minVaule;
minVaule = temp;
}
}
a[i] = minVaule; //把一趟的结果存起来
printTemp(a, i);
}
}
public void printTemp(int a[], int i) {
System.out.print("第" + (i + 1) + "趟：");
for (int j = 0; j < a.length; j++) {
if (j == 0) {
System.out.print("[" + a[j] + "\t");
} else if (j == i) {
System.out.print(a[j] + "]\t");
} else {
System.out.print(a[j] + "\t");
}
}
System.out.print("\n");
}
public void print(int a[], int n) {
for (int j = 0; j < n; j++) {
System.out.print(a[j] + "\t");
}
System.out.print("\n");
}
选择排序算法优化——二元选择排序
上述排序一趟只记录一个最小值，如果我们一趟排序分别记录最小值和最大值，就可以减半我们外层循环次数，这种优化即二元选择排序
排序过程：
image.png
比上面一种直接选择排序少循环了一半的次数，只增加了最大值的选择过程。
代码实现：
@Test
public void SmartSelectSort() {
int a[] = {3, 1, 5, 7, 2, 4, 9, 6, 10, 8};
SelectSort selectSort = new SelectSort();
System.out.print("smart Select brefore:");
selectSort.print(a, a.length);
selectSort.SmartSelectSort(a, a.length);
System.out.print("smart Select after:");
selectSort.print(a, a.length);
}
public void SmartSelectSort(int a[], int n) {
for (int i = 0; i < n / 2; i++) {
int minVaule = a[i]; //一趟预置最小值--第一个
int maxVaule = a[n - i - 1]; //一趟预置最大值--最后一个
int temp;
for (int j = i ; j < n - i; j++) {
if (minVaule > a[j]) {
temp = a[j];
a[j] = minVaule;
minVaule = temp;
}
if (maxVaule < a[j]) {
temp = a[j];
a[j] = maxVaule;
maxVaule = temp;
}
}
a[i] = minVaule; //把一趟的结果存起来
a[n - i - 1] = maxVaule;
printSmart(a, i + 1);
}
}
public void printSmart(int a[], int i) {
System.out.print("第" + i + "趟：");
for (int j = 0; j < a.length; j++) {
if (j == 0) {
System.out.print("[" + a[j] + "\t");
} else if (j == i - 1) {
System.out.print(a[j] + "]\t");
} else if (j == a.length - i) {
System.out.print("[" + a[j] + "\t");
} else if (j == a.length - 1) {
System.out.print(a[j] + "]");
} else {
System.out.print(a[j] + "\t");
}
}
System.out.print("\n");
}
