N^2排序算法总结

姓名：王怀帅  学号：16040410035

转载自：http://www.jianshu.com/p/c58eadf8db34=有修改

【嵌牛导读】：使用N^2复杂度的优缺点以及分类

【嵌牛鼻子】：N^2排序算法

【嵌牛提问】：如何来优化N^2算法？

【嵌牛正文】：

选择排序

算法的图解

SetectSort.gif

算法的基本实现

根据上面的gif图可以得到，实现选择排序需要两个步骤

找到第i个元素后的最小的数字

for (int i = 0; i < myArray.length; i++) {

minIndex=i; //假设最小值为i

//寻找最小值

for (int j = i; j < myArray.length; j++) {

if (myArray[minIndex]>myArray[j]) minIndex=j;

}

交换最小位置的元素和第i个位置的元素

Utils.swap(myArray,i,minIndex);

交换方式的一个小结

插入排序

动态演示

InstallSort.gif

算法的基本实现

判断当前索引的元素与其前面的数据进行比较

for (int i = 1; i < myArray.length; i++) {

for (int j = i; j >0; j--) {

}

}

如果小于前面的索引，则进行位置交换

if (myArray[j]

Utils.swap(myArray,j,j-1);

算法的优化

优化演示

优化

起因：因为交换数据每次都需要，创建三个变量，效率十分的低，我们需要用一种方式，使得不需要交换数据也能实现功能

方法：将当前索引的位置的数据进行copy，用这个拷贝值与前面的数据进行比较，如果小于前面的数据，则前面的数据向后移动，直到，copy值大于前面的某一个值，然后替换到该位置

实现

for (int i = 1; i < myArray.length; i++) {

int e=myArray[i];    //记录当前索引的值

int j;              //方面与最后位置索引进行数据赋值

for (j = i; j >0 && e < myArray[j-1]; j--)

myArray[j]=myArray[j-1];    //比当前索引值大的数据整体位置向后移动

myArray[j]=e;          //将拷贝值放入正确位置

}

算法的使用场景

如果当前数据本身是相对有序的，那么插入算法相比其他算法效率更高。

如果数据本身是无序的，那么，选择O(n*logn)的方法

冒泡排序

算法的动画演示

BubbleSort.gif

算法的基本实现

遍历数组

for (int i = 0; i < array.length; i++)

找出在i位置真正的数据，也就是i后的最小值，放入i的位置

for (int j = array.length-1 ; j > i; j--) { //注意这里一定要大于i否则会产生越界的问题

if (array[j]

Utils.swap(array,j,j-1);

}

三种算法的比较

选择排序插入排序冒泡排序

使用场景效率低少使用要处理的数据本生的有序性好，可以使用效率低谨慎使用