排序算法

• 冒泡(Bubble)
• 选择
• 插入
• 归并
• 快速
• 计数排序

冒泡排序

简单的说就是，每一次遍历都把最大(小)的通过比较选出来。

1. 从第一个元素开始比较相邻的两个元素，把大（小）的往后移；
2. 比较到未排序的最后一个元素时，会得出这趟冒泡得到的最大（小）元素；
3. 一直遍历到只有一个元素

代码实现：

(java)
int []a = {5,4,3,2,1,12,32,13,24,53};
        
        for (int i = a.length - 1 ; i >0; i--){
            for (int j = 0;j< i;j++){
                if(a[j] > a[j+1])
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }

选择排序

这个算法也很简单，每次都把未排序序列里最小（大）的选出来，放在序列。

1. 一趟遍历未排序序列，选出最小（大）的数字；
2. 把这个数字放在未排序序列前面，*未排序序列 + 1
3. 重复步骤到完成排序。

代码实现：

int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        
        for (int i = 0; i<a.length;i++){
            int min = a[i];
            int mark = i;
            for(int j = i ;j <a.length ; j++){
                if( min > a[j]) 
                    {
                        min = a[j];
                        mark = j;
                    }
            }
            int temp = a[i];
            a[i] = min;
            a[mark] = temp;
            
        }

插入排序

排序流程：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤 2~5

实现代码：

package Sort;

public class InsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        
        for (int i = 1;i<a.length;i++){
            int temp = a[i];
            for (int j = i - 1 ; j>=0 ; j--){
                if(temp < a[j]){
                    a[j+1] = a[j];
                    a[j] = temp;
                    
                }else{
                    break;
                }
            }

        }
        
        for (int i = 0 ; i< a.length ; i++)
            System.out.print(a[i]+" ");
    }

}

归并排序

归并排序采用呢，采用了分治法来让两个数组归并。

排序流程：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤 3 直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

public static int[] sort(int[] nums, int low, int high) {  
        int mid = (low + high) / 2;  
        if (low < high) {  
            // 左边  
            sort(nums, low, mid);  
            // 右边  
            sort(nums, mid + 1, high);  
            // 左右归并  
            merge(nums, low, mid, high);  
        }  
        return nums;  
    }  
    
    public static void merge(int[] nums, int low, int mid, int high) {  
        int[] temp = new int[high - low + 1];  
        int i = low;// 左指针  
        int j = mid + 1;// 右指针  
        int k = 0;  
  
        // 把较小的数先移到新数组中  
        while (i <= mid && j <= high) {  
            if (nums[i] < nums[j]) {  
                temp[k++] = nums[i++];  
            } else {  
                temp[k++] = nums[j++];  
            }  
        }  
  
        // 把左边剩余的数移入数组  
        while (i <= mid) {  
            temp[k++] = nums[i++];  
        }  
  
        // 把右边边剩余的数移入数组  
        while (j <= high) {  
            temp[k++] = nums[j++];  
        }  
  
        // 把新数组中的数覆盖nums数组  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            nums[k2 + low] = temp[k2];  
        }  
    }
    
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        MergeSort.sort(a, 0, a.length-1);
        
        for (int i = 0 ; i< a.length ; i++)
            System.out.print(a[i]+" ");

    }

快速排序