排序算法展示

排序定义及其性质

一、冒泡排序

  冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

  它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

  这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

二、选择排序

  选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

三、插入排序

  插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,算法适用于少量数据的排序，时间复杂度O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

四、希尔排序

  希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

  希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

四、归并排序

  归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为**二路归并**。归并排序是一种稳定的排序方法。

五、快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。

  快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

排序算法题目示例：

75. 颜色分类

1、冒泡排序

void sortColors(vector<int>& nums) {
	for (int i = 0; i < nums.size()-1; i++) {
		for (int j = 0; j < nums.size()-i-1; j++) {
			if (nums[j] > nums[j+1]) {
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
			}
			
		}
	}

}

2、选择排序

void sortColors(vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++) {
		int min = i;
		for (int j = i+1; j < nums.size(); j++) {
			if (nums[min] > nums[j]) {
				min = j;
			}

		}
		if (min != i) {
			int temp = nums[i];
			nums[i] = nums[min];
			nums[min] = temp;
		}
	}

}

3、三路插入排序

public void sortColors(int[] nums) {
        int zero = -1; //nums[0……zero] =0
        int two = nums.length; //nums[two……n) =2

        for(int i = 0;i < two;){
            if(nums[i] == 1){
                i++;
            }else if(nums[i] == 2){
                swap(nums,i,--two);
            }else{
                swap(nums,i++,++zero);
            }
        }
    }
      public void swap(int nums[],int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

88. 合并两个有序数组

1、二路归并法

public void merge(int[] nums1, int m, int[] nums2, int n) {
       int[] newNums = new int[m+n];
       int i=0,j=0,k=0;
       while (i<m&&j<n) {
           newNums[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
       }
       while (i < m){
           newNums[k++] = nums1[i++];
       }
       while (j < n) {
           newNums[k++] = nums2[j++];
       }

       for(int l =0;l< newNums.length;l++){
           nums1[l] = newNums[l];
           System.out.print(nums1[l]+" ");
       }
   }

215. 数组中的第K个最大元素

1、冒泡法优化版

public int findKthLargest(int[] nums, int k) {
       int n = nums.length;
       int kk = nums.length - k;
       do{
           int index = 0;//排序辅助坐标点 在nums(index……n)中是有序的
           for (int i = 0; i < nums.length - 1; i++) {
               if (nums[i] > nums[i + 1]) {
                   int temp = nums[i];
                   nums[i] = nums[i + 1];
                   nums[i + 1] = temp;

                   index = i;//记录最后一次交换的坐标
               }
           }
           n = index;
           if (index < kk) return nums[kk];
       }while(n > 0);
       return nums[kk];
   }

2、快速排序法

public int findKthLargest(int[] nums, int k) {
       quickSort(nums,0,nums.length-1,k);
       return nums[nums.length-k];
   }
   public void quickSort(int[] nums ,int start,int end,int k) {
       int l = start ,r = end;
       int pivort = nums[l];
       while(l<r){
           while((l<r)&&nums[l]<pivort)
               l++;
           while((l<r)&&nums[r]>pivort)
               r--;
           if((l<r)&&nums[l]==nums[r])
               l++;
           else {                
               int temp = nums[l];                
               nums[l] = nums[r];                
               nums[r] = temp;            
           } 
       }
       if((l-1)>start)quickSort(nums,start,l-1,k);
       if((r+1)<end)quickSort(nums,r+1,end,k);
      
   }

912. 排序数组

1、插入排序法

class Solution {
    public int[] sortArray(int[] nums) {
       if(nums.length < 2)return nums;
       for(int i =1;i<nums.length;i++){
            int current = nums[i];
            int j =i-1;
            while(j>=0&&nums[j]>current)
                    nums[j+1] = nums[j--];
             nums[j+1] =current; 
       }
       return nums;
    }
}

2、希尔排序

  1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

class Solution {
    public int[] sortArray(int[] nums) {
       if(nums.length < 2)return nums;
       for(int gap =nums.length/2;gap>0;gap =gap/2){
            for(int i =gap;i<nums.length;i+=gap){
                    int current = nums[i];
                    int j =i-gap;
                    while(j>=0&&nums[j]>current){
                            nums[j+gap] = nums[j];
                            j-=gap;
                    }
                    nums[j+gap] =current; 
            }
       }
       return nums;
    }
}

3、归并排序

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length < 2)return nums;
        return mergeSort(nums,0,nums.length-1);
    }
    private int[] mergeSort(int[] nums,int l,int r) {
        if(l==r)return new int[]{nums[l]};
        int mid = l+(r-l)/2;
        int[]numsLeft = mergeSort(nums,l,mid);//左有序数组
        int[]numsRight = mergeSort(nums,mid+1,r);//右有序数组
        int []newNums = new int[numsLeft.length+numsRight.length];//开辟新有序数组空间

        int i = 0,j=0,k=0;
        while(i<numsLeft.length&&j<numsRight.length)
            newNums[k++] = numsLeft[i]<numsRight[j]?numsLeft[i++]:numsRight[j++];
        while(i<numsLeft.length)
          newNums[k++] = numsLeft[i++];
        while(j<numsRight.length)
          newNums[k++] = numsRight[j++];

        return newNums;

    }

}

参考：十大经典排序算法（动图演示）