数据结构基础-十种排序方式

排序分类

sortClass.PNG

1.冒泡排序

冒泡排序从第一个数开始和后一个数开始比较，慢慢的最大（最小的数）就会浮到数列的顶端
1.比较相邻的两个数，如果第一个数比第二个大，则交换他们的位置
2.对每一对相邻的元素做第一步的操作，最后一个数就一定是最大的那个数
3.第二步结束后，我们确保数列的最后的那个数是最大的
4.重复前三步，直到次数等于数列大小（因为重复一次操作能排好一个最大的数,n次则排好n个）

bubble sort.PNG

上图为第一步和第二步，我们可以得到最后一个数是最大的，于是在下轮循环时，最后一个是可以不用比较的

 static  void sort(int[] intarry){
        for(int i=0;i<intarry.length;i++){
            for(int j=0;j<intarry.length-i-1;j++){
                if(intarry[j]>intarry[j+1]){
                    int temp=intarry[j];
                    intarry[j]=intarry[j+1];
                    intarry[j+1]=temp;
                }
            }
        }
    }

算法分析

• 最好情况:T(n)=O(n) 为什么是n,因为在第一轮时，如果一个元素都没有交换，我们可以直接break，因为已经是排好序的了
• 最差情况:T(n)=O(n^2)
• 平均情况:T(n)=O(n^2)

为什么时间复杂度是O^2,由上面的算法可知 第一次循环 需要n次，第二次需要n-1次，以此类推 n+n-1+n-2+....+1 =n*(n-1)/2，为什么是O(n^2 )呢，时间复杂度表示数量级，当n很大时候，n和/2都可以忽略掉.所以是O(n^2)

ps：排序100000个随机数时，算法花费的时间为19549ms (电脑不同，时间也不相同，但是可以比较各个算法大致的时间)

2.直接插入排序

1.默认第一个数已经是排好序的，从第二个数开始，从后往前扫描
2.把当前需要插入的数保存起来，与已经排好序的数列进行比较，如果该数比前面一个数要小，则前一个数向后移动
3.重复第二步，直到找到已排序的元素小于或者等于新元素的位置
4.将当前数插入到该位置后
5.重复前234步，直到遍历完整个数组

 /**
     * 从第二个数开始，从后向前扫描 eg  4321 -> 3421-> 3 4 2 1 -> 3 2 4 1->2 3 4 1 two will copm three and four and change the position
     *  insertion sort will stop  when it found the num
     * @param intarry
     */
    static  void insertionSort(int[] intarry){
        for(int i=0;i<intarry.length-1;i++){
           int current=intarry[i+1];
           int lastIndex=i;  //last num
           while(lastIndex>=0 && current<intarry[lastIndex]){
               intarry[lastIndex+1]=intarry[lastIndex];
               lastIndex--;
           }
           intarry[lastIndex+1]=current;
        }
    }

未完待续