总结.png

选择排序

算法的图解

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]<myArray[j-1])
            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]<array[j-1]){
        Utils.swap(array,j,j-1);
  }

三种算法的比较