排序算法展示
排序定义及其性质
一、冒泡排序
冒泡排序（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;
}
} 
京公网安备 11010502036488号