各种选择+冒泡+插入排序图解

文字描述：对一个序列A中的元素A[1]~A[n],令i从1到n枚举，进行n趟操作，每趟从待排序部分【i,n】中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间【1,,i-1】形成新的有序区间【1,i】。于是n趟操作后，元素就会是有序的。

图形描述：
存储状态：

初始序列：{49 27 65 97 76 12 38}
　　第1趟：12与49交换：12{27 65 97 76 49 38}
　　第2趟：27不动　：12 27{65 97 76 49 38}
　　第3趟：65与38交换：12 27 38{97 76 49 65}
　　第4趟：97与49交换：12 27 38 49{76 97 65}
　　第5趟：76与65交换：12 27 38 49 65{97 76}
　　第6趟：97与76交换：12 27 38 49 65 76 97 
  完成

void SelectSort(RecordType r[], int length)　/*对记录数组r做简单选择排序，length为待排序记录的个数*/
{
    int temp;
    for ( i=0 ; i< length-1 ; i++) //n-1趟排序
    {
        int index=i；　//假设index处对应的数组元素是最小的
        for (int j=i+1 ; j < length ; j++) 　//查找最小记录的位置
            if (r[j].key < r[index].key )
                index=j;
        if ( index!=i) 　//若无序区第一个元素不是无序区中最小元素，则进行交换
        {
            temp     = r[i];
            r[i]     = r[index];
            r[index] = temp;
        }
    }
}

O(n^2)

文字描述：它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！

基本原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

图片描述：

void bubbleSort (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) //外循环为排序趟数，len个数进行len-1趟
        for (j=0; j<len-1-i; j++) { // 内循环为每趟比较的次数，第i趟比较len-i次
            if (arr[j] > arr[j+1]) { // 相邻元素比较，若逆序则交换(升序为左大于右，降序反之)
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

O(N^2)

文字描述过程：
第1趟插入：将第2个元素插入前面的有序子序列，此时前面只有一个元素，当然是有序的
第2趟比较：将第3个元素插入前面的有序子序列，前面的2个元素是有序的
......
第n-1趟比较：将第n个元素插入前面的有序子序列，前面n-1个元素是有序的

图片描述（第一种）：

图片描述（第二种）：

public static void insertionSort(int[] nums) {
    int temp;
    for(int i = 1; i < nums.length; i++) {
        for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
            temp = nums[j];
            nums[j] = nums[j + 1];
            nums[j + 1] = temp;
        }
    }
}

O(n^2)

上面的算法的缺点：在第i-1趟插入时，需要把第i个元素插入到前面的i-1个元素中，该算法总是从i-1个元素开始逐个比较之前的每个元素，直到找到第i个元素的插入位置，这显然没有利用前面0~i-1个元素已经有序的特点。

优化：在0~i-1个有序元素给第i个元素寻找插入的位置时，使用二分查找法可以有效提高查找插入位置的时间效率，经过优化的插入排序称为折半插入排序

public static void binaryInsertionSort(int[] nums) {
    for(int i = 1; i < nums.length; i++) {
        int left = 0;
        int right = i - 1;
        int temp = nums[i];
        // 通过二分查找找到插入的位置
        while(left <= right) {
            int mid = (left + right) / 2;
            if(temp > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 插入位置之后的元素依次向后移动
        for(int j = i; j > left; j--) {
            nums[j] = nums[j - 1];
        }
        // 更新插入位置的值
        nums[left] = temp;
    }
}

1.函数的使用必须加上头文件#include<algorithm> 和using namespace std;
2.sort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数（非必填）)
3.通常是sort(a,a+len,cmp())
不写比较函数的话，默认从小到大排序
4.通常与vector容器配合使用（想了解的请点击如下链接）

bool cmp(int a,int b){
    return a>b;
}

struct node{
    int x;
}；
bool cmp(node a,node b){
    return a.x<b.x;
}

struct node{
    int x;
    int y;
}；
bool cmp(node a,node b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y>b.y;
}

struct node{
    char x[100];
    char y[100];
}；
bool cmp(node a,node b){
    if(a.x!=b.x) return strcmp(a.x,b.x)<0;
    else return strcmp(a.y,b.y)>0;
}