WJP
919497158@qq.com
冒泡、选择、插入排序

1.冒泡排序

指针重复地走访过要排序的数列,一次比较两个元素,并排序。重复地进行直到排序完成。共比较(n-1)+(n-2)+(n-3)+···+1次。

以下是JAVA实现代码:

public class BubbleSort {
    public static void sort(int[] a) {
        for(int i=a.length-1;i>=0;i--){ //i控制比较的轮数
            for(int j=0;j<i;j++){ //j每一轮比较的次数
                if(a[j]>a[j+1]){
                    a[j]=a[j]^a[j+1];
                    a[j+1]=a[j]^a[j+1];
                    a[j] = a[j]^a[j+1];
                }
            }
        }
    }
}

2.选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

图解:

这里写图片描述

以下是JAVA实现代码:

public class StraightSelectionSort {
    public static void sort(int a[]) {  
        int k=0;
        for(int i=0;i<a.length-1;i++){
            k=i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[k]){
                    k=j;
                }
            }
            if(k!=i){
                a[k] = a[k]^a[i];
                a[i] = a[k]^a[i];
                a[k] = a[k]^a[i];
            }
        }
    }
}

3.插入排序

时间复杂度,好情况下O(N)正序,差情况下O(N2)倒序。稳定性
先把第一个元素看做是一个已经排好序的数组,后面的元素依次往里面插入。
这里要注意,插入的时候要从最后一个元素开始对比。如果小就交换,交换结束后,依然要跟前一个元素进行对比,直到数组头或者前面的元素小于当前元素。这样不会覆盖掉前面的元素

示例:

1 2 6 7 | 4  (4对比7,交换)
1 2 6 4 | 7  (4对比6,交换)
1 2 4 6 | 7  (4对比2,不动,移动 | ,排好序的数组元素+1)
1 2 4 6 7 |

以下是JAVA实现代码:

public static void insertionSort(int[] arr) {
		if(arr==null||arr.length<2)
			return;
		for(int i=1;i<arr.length;i++)
		{
			for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--)
                                int temp=arr[j+1];
                                arr[j+1]=arr[j];
                                arr[j]=temp;       
		}
	}

wjp

文章作者

发表评论

textsms
account_circle
email

冒泡、选择、插入排序
1.冒泡排序 指针重复地走访过要排序的数列,一次比较两个元素,并排序。重复地进行直到排序完成。共比较(n-1)+(n-2)+(n-3)+···+1次。 以下是JAVA实现代码: public class Bubble…
扫描二维码继续阅读
2020-07-21