八种基本算法和代码讲解（默认从小到大排序）

一 冒泡排序
通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”

-时间复杂度
最好情况下：正序有序，则只需要比较n次。故，为O(n)
最坏情况下: 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N*N)
代码演示

public void Merge(int[] str)  //冒泡排序
    {
        int temp;
        for(int i=1;i<str.length;i++)   //  进行n次如下的操作
        {
            for(int j=0;j<str.length-i;j++)   // 这个遍历实际上是取出最大的数放到最后的位置
            {
                if(str[j]>str[j+1])
                {
                    temp=str[j];
                    str[j]=str[j+1];
                    str[j+1]=temp;
                }
            }
        }
    }

二 选择排序

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。
-时间复杂度
最好情况下：交换0次，但是每次都要找到最小的元素，因此大约必须遍历NN次，因此为O(NN)。减少了交换次数！
最坏情况下，平均情况下：O(N*N)
代码演示

public void selectMerge(int[] str)
    {
        for(int i=0;i<str.length;i++)     //  进行N此如下的循环
        {
            int min=i;   //假设一开始第一个最小
            for(int j=i+1;j<str.length;j++)     // 将后面的数与前面的比较，取出最小的数放到最前的位置
            {
                int temp;
                if(str[min]>str[j])
                {
                    temp=str[min];
                    str[min]=str[j];
                    str[j]=temp;
                }
            }
        }
    }

三 直接插入排序(插入排序)

每次选择一个元素K插入到之前已排好序的部分A[1…i]中，插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面，插入前需要移动元素
-时间复杂度
最好的情况下：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)
最坏的情况下：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n­2)
平均情况下：O(n­2)
代码演示

void insertmerge(int[] arr)
    {
        for(int i=1;i<arr.length;i++)    //  从第一个数开始与前面数组比较，进行N-1次循环
        {
            int temp=arr[i];//temp标记为未排序第一个元素
            int j=i-1;
            while(j>=0 && arr[j]>temp)   // 取出一个数放到前面有序数组中恰当的位置
            {
                arr[j+1]=arr[j];
                j--;        
            }
            arr[j+1]=temp;
        }
    }

四 快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
简单说就是找个基准数，假如为第一个，然后从数据两头开始遍历，如果一边大于基准书，另外边小于基准数，那么调换这两个数据，当两头碰面时候也就是结束一次完整遍历对调。

代码演示

void quicksort(int left,int right) 
{ 
    int i,j,t,temp; 
    if(left>right) 
       return; 

    temp=a[left]; //temp中存的就是基准数 
    i=left; 
    j=right; 
    while(i!=j) 
    { 
                   //顺序很重要，要先从右边开始找 
                   while(a[j]>=temp && i<j) 
                            j--; 
                   //再找右边的 
                   while(a[i]<=temp && i<j) 
                            i++; 
                   //交换两个数在数组中的位置 
                   if(i<j) 
                   { 
                            t=a[i]; 
                            a[i]=a[j]; 
                            a[j]=t; 
                   } 
    } 
    //最终将基准数归位 
    a[left]=a[i]; 
    a[i]=temp; 

    quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 
    quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程 
}