碎碎念：

         记得当初第一年的时候、接触算法、有那么两个视频、跳舞的、讲的是冒泡排序跟选择排序、当时看了好多遍终于懂了、这次多了一些算法、学起来也还好吧、咱是有基础的人、找到了以前的视频、有的就发了、没找到的就没法、其实算法并不难、绕绕就明白了、先别看代码- -

思维导图

插入排序

从头到尾巴、从第二个开始、向左进行插入、这里说的插入是指作比较、直到比较出比自己小的就插入到他的前面。

例子

         1 7 4 8 6 5

          插入排序

         [1]7 4 8 6 5

         [1 7] 4 8 6 5   

         [1 4 7]  8 6 5  

         [1 4 7 8 ] 6 5  

         [1 4 6 7 8 ] 5 

         [1 4 5 6 7 8 ]

 特性

        算法是稳定的、时间复杂度为O(n2)、空间复杂度为O（1）、需要一个辅助的空间变量

代码（java）

<span style="font-size:18px;">// insert_sort
    publicint[] insert_sort(int[] arr) {
       int[] intArr = arr;
       int i, j, key;
       for (j = 1; j < intArr.length; j++) {
           key = intArr[j];
           i = j - 1;
           while (i >= 0 && intArr[i] > key) {
              intArr[j] = intArr[i];
              i--;             
           }
           intArr[i + 1] = key;
       }
       return intArr;
    }</span>

小编：咳咳咳、这次也自称小编了、其实插入排序真的没啥- -、就是一个个往有序序列里面插入新的数值。

视频（插入）

交换排序

        交换排序其实就是两个值相互比较的思想、如果后面的值比前面的小、就交换位置（从小到大排序）、交换排序一般有冒泡排序、快速排序两种。

冒泡排序

         第一次听说这个算法就想到了儿时家里养的金鱼、常常看它吐泡泡、（虽然不久它就不在了）、但是思想很明显、那就是气泡在水里会上浮、所谓的冒泡排序就是从头到位、依次两个值做比较、如果后面的值比前面小、两个值就交换、每次都可以交换出一个’最大值‘，就好像大泡泡上浮一样。

例子（相邻的两个数交换、每循环一次交换就能找出一个最大的）

特性：时间复杂度为O(n2)是稳定的算法、但是数据大的时候不建议使用。

代码

<span style="font-size:18px;">void BubbleSort3(int a[], int n)
{
	int j, k;
	int flag;
	
	flag = n;
	while (flag > 0)
	{
		k = flag;
		flag = 0;
		for (j = 1; j < k; j++)
			if (a[j - 1] > a[j])
			{
				Swap(a[j - 1], a[j]);
				flag = j;
			}
	}
}</span>

视频（冒泡）

快速排序

              其实是冒泡排序的一种改进、取一个键值、然后与其他值相比较、比键值大的放后面键值小的放前面（交换）、循环一次的效果就是比键值大的都在前面了、比键值小的都在后面了、然后再在前面那半取一个键值、循环上边步骤、不断划分、直到排序完成。

例子：

特性：时间复杂度为O(nlog2n)、不稳定！平均时间最佳！最坏情况近似O(n2)

代码

<span style="font-size:18px;">#include<iostream>  
using namespace std;  
void quickSort(int a[],int,int);  
int main()  
{  
    int array[]={34,65,12,43,67,5,78,10,3,70},k;  
    int len=sizeof(array)/sizeof(int);  
    cout<<"The orginal arrayare:"<<endl;  
    for(k=0;k<len;k++)  
        cout<<array[k]<<",";  
    cout<<endl;  
    quickSort(array,0,len-1);  
    cout<<"The sorted arrayare:"<<endl;  
    for(k=0;k<len;k++)  
        cout<<array[k]<<",";  
    cout<<endl;  
    system("pause");  
    return 0;  
}  
  
void quickSort(int s[], int l, int r)  
{  
    if (l< r)  
    {        
        int i = l, j = r, x = s[l];  
        while (i < j)  
        {  
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数  
                j--;   
            if(i < j)  
                s[i++] = s[j];  
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数  
                i++;   
            if(i < j)  
                s[j--] = s[i];  
        }  
        s[i] = x;  
        quickSort(s, l, i - 1); // 递归调用  
        quickSort(s, i + 1, r);  
    }  
}  </span>

视频（快速）

选择排序

直接选择排序

          这个真的简单的不想说了= = 、有一行数、每次都选择一个最小的出来、如图

<span style="font-size:18px;">//为了使用Random类，需要加入如下这行：
import java.util.*;
/**
 * 直接选择排序算法的Java实现。<br/>
 *   1：从a[0]-a[N-1]中选出最小的数据，然后与a[0]交换位置<br/>
 *   2：从a[1]-a[N-1]中选出最小的数据，然后与a[1]交换位置（第1步结束后a[0]就是N个数的最小值）<br/>
 *   3：从a[2]-a[N-1]中选出最小的数据，然后与a[2]交换位置（第2步结束后a[1]就是N-1个数的最小值）<br/>
 *   以此类推，N-1次排序后，待排数据就已经按照从小到大的顺序排列了。<br/>
 * 此代码作为课件提供给学生参考，在学完数组、循环、判断后练习。<br/>
 * @author luo_wenqiang@126点com
 * @version 1.0.0
 */
public class 直接选择排序
{
    public static void main(String[] args) 
    {
        //声明一个数组
        int[] array = new int[10];
        //为这个数组随机填入整型数字
        Random random = new Random();
        for (int i = 0; i < array.length ; i++)
        {
            array[i] = random.nextInt(500);
        }
  
        System.out.print("原始数组  ：");
        System.out.println(Arrays.toString(array));
        /****************************************
         下面开始正式的“直接选择排序”算法
         直接选择排序的关键：
            1：从a[0]-a[N-1]中选出最小的数据，然后与a[0]交换位置
            2：从a[1]-a[N-1]中选出最小的数据，然后与a[1]交换位置（第1步结束后a[0]就是N个数的最小值）
            3：从a[2]-a[N-1]中选出最小的数据，然后与a[2]交换位置（第2步结束后a[1]就是N-1个数的最小值）
            以此类推，N-1次排序后，待排数据就已经按照从小到大的顺序排列了。
         ****************************************/
         //N个数组元素，就需要循环N轮
         for(int i = 0; i < array.length; i++){
             //最小数的索引，该索引每次都根据外层循环的计数器来觉得初始值。
             int minIndex = i;
             for (int j = i; j < (array.length); j++)
             {
                 //根据最小数的索引，判断当前这个数是否小于最小数。
                 //如果小于，则把当前数的索引作为最小数的索引。
                 //否则不处理。
                 if(array[minIndex] > array[j]){
                     minIndex = j;
                 }
                 //直到循环完成的时候，minIndex肯定就是当前这轮循环中，最小的那个。
             }
             //System.out.print(i + "轮，最小数" + array[minIndex] + "，");
             //System.out.print("原索引" + minIndex + "，新索引" + i);
             //得到最小数的索引后，把该索引对应的值放到最左边，并且把最左边的值放到索引所在的位置.
             //最左边的值
             int temp = array[i];
             //把最小数索引对应的值放到最左边
             array[i] = array[minIndex];
             //把原来最左边对应的值放到最小数索引所在的位置
             array[minIndex] = temp;
             System.out.println(String.format("%2s",(i + 1)) + "轮排序后：" + Arrays.toString(array));
         }
    }
}</span>

堆排序

简单的了解下堆、堆分最大堆和最小堆、最大堆跟比也子节点大、最小堆相反

最大堆和最小堆

如果从小到大用堆排序、每次都把最小堆的根输出、然后用堆的最后一层最右边的叶子节点补上去、然后进行堆排序（从节点数除以2的根开始排序）、选出最小根、输出、依次这样直到堆的数都输出完。

这里最重点的其实是堆排序

推荐一篇博客吧

http://blog.csdn.net/genios/article/details/8157031

归并

二路归并排序

把每两个数分成一组、相比较、如果顺序不对就交换顺出、循环一次之后、把两个分组合成一个分组、这时候这个分组有四个数、然后进行排序、依此循环、最总合并成一个组、就是按从大到小排序的了、发张图吧= =说的不太清。

代码

package　algorithm;
 
public　class　MergeSort　{
//　private　static　long　sum　=　0;
/**
　*　<pre>
　*　二路归并
　*　原理：将两个有序表合并和一个有序表
　*　</pre>
　*　
　*　@param　a
　*　@param　s
　*　第一个有序表的起始下标
　*　@param　m
　*　第二个有序表的起始下标
　*　@param　t
　*　第二个有序表的结束小标
　*　
　*/
private　static　void　merge(int[]　a,　int　s,　int　m,　int　t)　{
int[]　tmp　=　new　int[t　-　s　+　1];
int　i　=　s,　j　=　m,　k　=　0;
while　(i　<　m　&&　j　<=　t)　{
if　(a[i]　<=　a[j])　{
tmp[k]　=　a[i];
k++;
i++;
}　else　{
tmp[k]　=　a[j];
j++;
k++;
}
}
while　(i　<　m)　{
tmp[k]　=　a[i];
i++;
k++;
}
 
while　(j　<=　t)　{
tmp[k]　=　a[j];
j++;
k++;
}
System.arraycopy(tmp,　0,　a,　s,　tmp.length);
}
 
/**
　*　
　*　@param　a
　*　@param　s
　*　@param　len
　*　每次归并的有序集合的长度
　*/
public　static　void　mergeSort(int[]　a,　int　s,　int　len)　{
int　size　=　a.length;
int　mid　=　size　/　(len　<<　1);
int　c　=　size　&　((len　<<　1)　-　1);
//　-------归并到只剩一个有序集合的时候结束算法-------//
if　(mid　==　0)
return;
//　------进行一趟归并排序-------//
for　(int　i　=　0;　i　<　mid;　++i)　{
s　=　i　*　2　*　len;
merge(a,　s,　s　+　len,　(len　<<　1)　+　s　-　1);
}
//　-------将剩下的数和倒数一个有序集合归并-------//
if　(c　!=　0)
merge(a,　size　-　c　-　2　*　len,　size　-　c,　size　-　1);
//　-------递归执行下一趟归并排序------//
mergeSort(a,　0,　2　*　len);
}
 
public　static　void　main(String[]　args)　{
int[]　a　=　new　int[]　{　4,　3,　6,　1,　2,　5　};
mergeSort(a,　0,　1);
for　(int　i　=　0;　i　<　a.length;　++i)　{
System.out.print(a[i]　+　"　");
}
}
}

算法复杂度与特性总结

总结：

        这些算法估计以后用都是别人封装好的、拿来直接用就行、但是用东西、要知道他的特性、数多的时候用哪个？数少的时候用哪个、什么时候用、其实算法也就那么回事、不要想太复杂、考试的话、时间复杂度主要考考、空间复杂度很少考、特性要考的、会出给一列数、让你用算法排序、把步骤写出来。

————————————高大上的算法————————————-

———————chenchen————————

【自考】排序算法-插入、交换、选择、归并排序