关于几种排序算法的快速理解方法

1.快速排序
这个是各大公司笔试面试最喜欢考的排序算法。
简单点说，就是先找一个数为“轴”（一般取第一个数即可），先从后向前扫描，找到比轴小的就交换，然后再从换过去的位置开始向后扫描，找到比轴大的就交换，然后重复上面的两步。最后分轴两边使用递归（这里面要多次使用while）。道理就这么简单！下面看代码：

#include<iostream>
using namespace std;
void quick_sort(int s[],int,int);
int main(){
    int a[10]={49,232,43,543,12,156,32,78,332,54};
    for(int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    quick_sort(a,0,9);
    for(int j=0;j<10;j++){
        cout<<a[j]<<" ";
    }
    cout<<endl;
    return 0;
}

void quick_sort(int s[],int start,int end){
    if(start<end){
        int i=start,j=end,x=s[start];    //x 为轴
        while(i<j){
            while(i<j&&s[j]>=x)
                --j;
            if(i<j)
                s[i]=s[j];
            while(i<j&&s[i]<x)
                ++i;
            if(i<j)
                s[j]=s[i];
        }
        // 将轴填充回去，然后递归
        s[i] = x;
        quick_sort(s,start,i-1);
        quick_sort(s,i+1,end);
    }
}

结果：


2. 冒泡排序
冒泡排序重点在于，如果数组长度为s，就会排s趟，然后每一趟都会搞定一个数，所以第i趟会比较 s-i 次。理解了这一点两层for循环就很容易写出来了。

#include<stdio.h>
int main(){
    int i,j,temp;
    int a[10];
    for(i=0;i<10;i++)
        scanf ("%d,",&a[i]);

    for(j=0;j<=9;j++){
        for(i=0;i<10-j;i++)
            if (a[i]>a[i+1]){
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
            }
        }
    }

    for(i=1;i<11;i++)
        printf("%5d,",a[i] );
    printf("\n");
    return 0;
}

3.插入排序
插入排序解决的是在已经有序的数列中插入一个数，然后数列仍然有序的算法。
重点在于，你需要有一个缓存的地方，然后使要插入的数一一与原数列中的数进行比较。找到合适的位置就插入。要注意数组可能越界的情况。
1）数组形式

void insertion_sort(int array[],int first,int last)
{
int i,j;
int temp;
for(i=first+1;i<=last;i++)
{
temp=array[i];
j=i-1;
//与已排序的数逐一比较，大于temp时，该数移后
while((j>=first)&&(array[j]>temp)){
array[j+1]=array[j];
j--;
}
array[j+1]=temp;
}
}

2）链表形式，更通用

void insert_sort(int* array,unsigned int n)
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--)
{
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}