排序算法笔记
2018-03-21 本文已影响0人
Xun_Moo
总结
排序算法.png
算法详解
tips：以下算法中均按从小到大排序
一 冒泡排序/Bubble Sort
思路
采用两两比较并交换位置的思路，就仿佛泡泡一样，较大的元素会慢慢“上浮”
- 从数列一端开始，比较相邻两个元素，如果第一个元素比第二个元素大，交换两个元素位置
- 移动至下一对相邻元素，再次进行比较和交换，直到数列最后一个元素
- 再次从最开始的一端开始两两比较和交换，直到数列的倒数第二个元素（因为上一次的遍历已经保证倒数第一的元素是数列中最大的）
- 不断重复以上操作。每次重复的时候，需要比较的元素个数都减1
复杂度
- 时间复杂度
- 最佳：O(n)
- 平均：O(n^2)
- 最差：O(n^2)
- 空间复杂度：O(1)
代码实现
public static void sort(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length-i-1; j++) {
if (numbers[j]> numbers[j+1]){//大数在前则交换位置
int temp = numbers[j+1];
numbers[j+1] = numbers[j];
numbers[j] = temp;
}
}
for (int num: numbers) {
System.out.println(num);
}
}
}
二 快速排序/Quick Sort
思路
- 选取一个合适的值，一般以头元素或尾元素
- 以选取值为基准，将数列分成两个子数列，大于基准值的在右边，小于或等于基准值的在左边
- 分别对基准值左右两边的的子序列重复第二步操作
- 重复第二、第三步直到子序列中只有一个元素
复杂度
- 时间复杂度
- 最佳：O(nlog n)
- 平均：O(nlog n)
- 最差：O(n^2)
- 空间复杂度：O(nlog n)
代码实现
public static void sort(int[] numbers,int left,int right){
if(left>=right){
return;
}
int tag = numbers[left];
int lo = left;
int hi = right;
while (left<right){
while ((tag<=numbers[right])&&(left<right)){
right--;
}
numbers[left] = numbers[right];
while ((tag>=numbers[left])&&(left<right)){
left++;
}
numbers[right] = numbers[left];
}
numbers[left] = tag;
sort(numbers,lo,left-1);
sort(numbers,left+1,hi);
}
三 插入排序/Insert Sort
思路
- 假设数列第一个元素为已排序数列，剩余数列为未排序
- 将待排序元素挨个插入到已排序数列中
- 每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置
复杂度
- 时间复杂度
- 最佳：O(n)
- 平均：O(n^2)
- 最差：O(n^2)
- 空间复杂度：O(1)
代码实现
public static void sort(int[] numbers){
int pre;
int current;
for (int i = 1; i < numbers.length ; i++) {//假定第一位已经排序，所以从number[1]开始，
pre = i - 1;
current = numbers[i];//记录待排序的数值
while ((pre>=0)&&(numbers[pre]>=current)){
numbers[pre+1] = numbers[pre];//将大于等于current的值往后挪一位
pre--;
}
numbers[pre+1] = current;
}
}
四 希尔排序/Shell Sort
希尔排序也被称为“缩小增量排序”
思路
- 选择一个间隔d，将数列中下标间隔为d的元素划分到同一组
- 对每一组做选择排序
- 减小d，并重复第一、第二步操作，直到d=1
复杂度
- 时间复杂度
- 最佳：O(n)
- 平均：O(nlog n)
- 最差：O(n^2)
- 空间复杂度：O(1)
代码实现
public static void sort(int[] numbers){
int div = numbers.length/2;//取第一个间隔
while (div>0){
for (int i = div; i < numbers.length ; i++) {//对每个区间做插入排序
int current = numbers[i];
int preindex = i-div;
while ((preindex>=0)&&(numbers[preindex]>current)){
numbers[preindex+div] = numbers[preindex];
preindex -= div;
}
numbers[preindex+div] = current;
}
div = div/2;
}
}
五 选择排序/Select Sort
思路
- 将数列分为已排序和未排序两部分
- 每次均从未排序的数列中选择最小的元素，插入到已排序部分的尾部
- 重复以上操作，知道未排序数列为空
复杂度
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
代码实现
public static void sort(int[] numbers){
int index = 0;
while (index < numbers.length-1){
int temp = numbers[index];
int current = index+1;
for (int i = index+1; i < numbers.length; i++) {//查找未排序数列中的最小值
if(temp>numbers[i]){
temp = numbers[i];
current = i;
}
}
//交换。将最小值放到未排序数列最前面
numbers[current] = numbers[index];
numbers[index] = temp;
index++;
}
}
六 堆排序/Heap Sort
思路
- 将数列中的元素构建成最大堆，作为无序区，记为H
- 将无序区的根元素Hn和最后一个元素H1交换位置，则Hn成为有序区，H1至H(n-1)成为新无序区
- 调整无序区，使其仍为最大堆
- 重复第二、第三步操作，直到所有元素都进入有序区
复杂度
- 时间复杂度：O(nlog n)
- 空间复杂度：O(1)
代码实现
public static void sort(int[] numbers){
int length = numbers.length;
//从后往前，构建最大堆
for (int i = length/2; i >=0 ; i--) {
toMaxHeap(numbers,i,length);
}
while (length>0){
//最大值移入有序区
int temp = numbers[0];
numbers[0] = numbers[length-1];
numbers[length-1] = temp;
length--;
toMaxHeap(numbers,0,length);
}
}
/**
* 将无序区调整为最大堆的方法
*/
public static void toMaxHeap(int[] numbers, int index, int length){
int left = index*2+1;
int right = index*+2;
int max_index = index;
if((left<length)&&(right<length)&&numbers[left]>numbers[right]){
max_index = left;
}else if((left<length)&&(right<length)&&numbers[left]<=numbers[right]){
max_index = right;
}
if(numbers[index]<numbers[max_index]){//不是最大堆，则调整一下
int temp = numbers[max_index];
numbers[max_index] = numbers[index];
numbers[index] = temp;
toMaxHeap(numbers,max_index,length);
}
}
七 归并排序/Merge Sort
思路
- 将数列平均分成两段
- 分别对两段数列进行归并排序
- 将两段有序的数列合并
简单来说，就是递归然后合并。
复杂度
- 时间复杂度：O(nlog n)
- 空间复杂度：O(n)
代码实现
public static void sort(int[] numbers, int begin, int end){
int mid = (begin+end)/2;
if(begin<end){
sort(numbers,begin,mid);//对左边进行排序
sort(numbers,mid+1,end);//对右边进行排序
merge(numbers,begin,mid,end);
}
}
public static void merge(int[] number, int low, int mid, int high){
int[] container = new int[high-low+1];//开辟临时存储区
int i = low;//第一个数组的起点
int j = mid+1;//第二个数组的起点
int index = 0;//临时存储区的下标
while ((i<=mid)&&(j<=high)){
//依次将较小的数放入container
if(number[i]<number[j]){
container[index] = number[i];
i++;
}else {
container[index] = number[j];
j++;
}
index++;
}
while (i<=mid){
container[index] = number[i];
i++;
index++;
}
while (j<=high){
container[index] = number[j];
j++;
index++;
}
for (int k = 0; k < container.length; k++) {
number[low+k] = container[k];
}
}
计数排序/Counting Sort
思路
非比较排序，待排序的数列需要是有限范围内的整数
- 获得数列的最大值和最小值
- 创建一个大小为最大值的数组，记为count
- 将数列中数值n的数量纪录在count[n]中
- 按count下标的顺序，反向填充原来的数列
复杂度
- 时间复杂度：O(n+k)
- 空间复杂度：O(k)
代码实现
public static void sort(int[] numbers){
int large = numbers[0];
int little = numbers[0];
//最大最小
for (int num:numbers) {
if(num>large){
large = num;
}else if(num<little){
little = num;
}
}
int[] count = new int[large+1];
for (int num:numbers) {
count[num]++;
}
int index = 0;
for (int i = little; i < count.length; i++) {
while (count[i]>0){
numbers[index++] = i;
count[i]--;
}
}
}
桶排序/Bucket Sort
思路
是对计数排序的改进。将数列按照一定的映射关系划分为大小相同的子区间，区间内元素排序，然后合并
- 获得数列的最大值和最小值
- ArrayList 作为桶，桶的数量为(max-min)/arr.length+1
- 遍历数列，计算每个元素所在的桶
- 每个桶各自排序
- 遍历桶数组，反向填充原来的数列
复杂度
- 时间复杂度
- 最佳/平均：O(n+k)
- 最差：O(n^2)
- 空间复杂度：O(n+k)
代码实现
public static void sort(int[] numbers){
int large = numbers[0];
int little = numbers[0];
//最大最小
for (int num:numbers) {
if(num>large){
large = num;
}else if(num<little){
little = num;
}
}
int bucketSize = numbers.length;//如果数据均匀的话，桶的大小不需要为数列的大小
int bucketNum = (large - little) / bucketSize + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
buckets.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i = 0; i < numbers.length; i++){
int index = (numbers[i] - little) / bucketSize;
buckets.get(index).add(numbers[i]);
}
//对每个桶进行排序
for(int i = 0; i < buckets.size(); i++){
Collections.sort(buckets.get(i));
}
int index = 0;
for (ArrayList<Integer> list:buckets) {
for (Integer i: list) {
numbers[index] = i;
index++;
}
}
}
基数排序/Radix Sort
思路
- 计算数组中的最大数，并计算其位数；
- 对数列中的每个元素，从最低位开始取每个位组成radix数组；
- 对radix数组进行计数排序；
- 重复第二、第三操作直到最大位数排序结束
复杂度
- 时间复杂度：O(n*k)
- 空间复杂度：O(n+k)
代码实现
public static void sort(int[] numbers) {//默认10进制
int large = numbers[0];
//最大数
for (int num : numbers) {
if (num > large) {
large = num;
}
}
int digit = String.valueOf(large).length();//最大位数
int mod = 10;
int dev = 1;
int bucketNum = 10;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
buckets.add(new ArrayList<Integer>());
}
for (int i = 0; i < digit; i++, dev *= 10, mod *= 10) {
for (int j = 0; j < numbers.length; j++) {
int bucket = (int) ((numbers[j] % mod) / dev);
buckets.get(bucket).add(numbers[j]);
}
int index = 0;
for (int k = 0; k < bucketNum; k++) {
ArrayList<Integer> list = buckets.get(k);
if (list.size()>0) {
for (Integer num:buckets.get(k)) {
numbers[index++] = num;
}
list.clear();//将桶清空
}
}
}
}
