总结.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);
}
三种算法的比较
| 选择排序 | 插入排序 | 冒泡排序 | |
|---|---|---|---|
| 使用场景 | 效率低少使用 | 要处理的数据本生的有序性好，可以使用 | 效率低谨慎使用 |
