排序算法总结：https://www.runoob.com/w3cnote/sort-algorithm-summary.html
一.冒泡排序：英文（BubbleSort）平均时间复杂度：O(n2)
1.基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
2.过程：（1）比较相邻的两个数据，如果第二个小，就交互位置。（2）从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。（3）继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
代码范例：是第一个数和最后一个数的比较
这样排序有个问题：数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
我们针对这个问题，我们解决方案是：就是给排序的的数据加标示符，例如给他加Bool 类型的，比较过了就是ture ，没有的是false。
代码范例：
二.选择排序：英文（SelctionSort）平均时间复杂度：O(n2)
1.基本思想：在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；第二次遍历n-2个数，找到最小的数值与第二个元素交换；第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
3.插入排序：英文（Insertion Sort） 平均时间复杂度：O(n2)
基本思想：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
4.哈希排序：英文 (Shell Sort) 平均时间复杂度O(n1.5)
基本思想：在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
5.快速排序：英文：(Quicksort) 平均时间复杂度 O(N*logN)
6.归并排序：英文：(Merge Sort) 平均时间复杂度 O(N*logN)
基本思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
7.堆排序(HeapSort)
平均时间复杂度：O(NlogN)
由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)
8.基数排序(RadixSort)
基本思想：BinSort想法非常简单，首先创建数组A[MaxValue]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。
public static void RadixSort(int A[],int temp[],int n,int k,int r,intcnt[]){
//A:原数组
//temp:临时数组
//n:序列的数字个数
//k:最大的位数2
//r:基数10
//cnt:存储bin[i]的个数
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
//初始化
for(int j=0;j<r;j++){
cnt[j] = 0;
}
//计算每个箱子的数字个数
for(int j=0;j<n;j++){
cnt[(A[j]/rtok)%r]++;
}
//cnt[j]的个数修改为前j个箱子一共有几个数字
for(int j=1;j<r;j++){
cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1;j>=0;j--){ //重点理解
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}
9.递归排序
这上面写的舒服：https://www.runoob.com/w3cnote/sort-algorithm-summary.html
网友评论