姓名：王怀帅 学号：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);
}
三种算法的比较
选择排序插入排序冒泡排序
使用场景效率低少使用要处理的数据本生的有序性好，可以使用效率低谨慎使用
网友评论