Android面试-算法学习
排序
选择排序
- 主要思想 在未排序序列中找出最小的元素，添加到有序序列中。
选择排序图解
- 思路：
- 将整个序列分为无序区和有序区，初始时候有序区为空，无序区含有待排序的所有记录。
- 在无序区中选取最小的元素，将它与无序区的第一个元素交换，使得有序区扩展了一位，同时无序区减少了一位。
- 重复 2 ，直到无序区只剩下一个记录为之。此时所有的记录已经从小到大排序完毕。
- 代码实现
public static void sort(int[] array){
int len = array.length;
for (int i = 0; i < len; i++){
//对n个元素进行n-1次简单排序
int index = i;
for(int j = i + 1; j < len; j++){
//在这层循环里面找出最小的元素
if(array[j] < array[index]){
index = j;
}
}
if(index != i){
int tem = array[i];
array[i] = array[index];
array[index] = tem;
}
}
}
冒泡排序（稳定）
冒泡排序，又称起泡排序。是交换排序中最简单的排序方法。
-
主要思想： 两两比较相邻的元素，如果反序则交换，直到没有反序。（反序就是违反序列规律，比如你要从小到大排序，但是两个元素 [5,2] 这样就反序了）
起泡排序图解.jpg -
思路：
- 将整个序列分为无序区和有序区，初始时候有序区为空，无序区含有待排序的所有记录。
- 对无序区从前到后依次相邻的元素两两比较，反序则交换，从而使较小的元素往前移，较大的元素往后移,，一趟下来无序区中最大的元素就会在无序区的最后了，我们把这个元素移除无序区放到有序区中。（像水中的起泡，体积大的先浮上来）
- 重复 2 ，直到无序区只剩下一个记录为之。此时所有的记录已经从小到大排序完毕。
-
再举个例子吧
初始元素序列 [50 , 13 , 55 , 97 , 27, 38, 49, 65] 方括号代表无序区第一趟排序结果 [13 , 50 , 55 , 27 , 38 , 49 , 65 ], 97 先是 50 和 13 比较，50>13，反序了，交换位置。
然后 50 和 55 比较，50<55，正常，下一个。
然后是 55 和 97 比较，55<97，正常，下一个。
然后是 97 和 27 比较，97>27，反序，交换位置。
···
如此类推，就把最大的元素97给放到最后了，此时97被排除出无序区，放进了有序区。大家可以把剩下几趟的排序结果自己排一下练手看看是否理解。
-
代码实现
public void sort(int[] array){ //第一层循环从数组最后往前遍历 for(int i = array.length - 1; i > 0; i--){ //这里循环上界是i-1，体现出每趟排序选出的最大值从无序区中转移到有序区中 for(int j = 0; j < i; j++){ if(array[j] > array[j+1]){ int tem = array[j]; array[j] = array[j+1]; array[j+1] = tem; } } } }
快速排序（不稳定）
快速是对冒泡排序的一种改进。在冒泡排序中，记录的比较和移动是两两相邻的元素，把较大的元素一步一步推到后面，因此总的比较次数和移动次数较多。而快速排序是从两端向中间进行的。较大的元素一下子就能从前面移动到后面，这样比较的次数和移动的次数就减少了。
-
主要思想：运用分治算法，找一个分割值key，然后将无序区元素分为小于 key 和大于 key的元素集，直到所有的分区只包含一个元素。
快速排序图解.jpg
-
思路：
- 选择分割值：最简单的方法是选择第一个元素作为分割值。
- 定义i、j 分别指向集合的最左和最右。
- 从右侧扫描小于key的，r[ i ] 和 r[ j ] 进行交换，并执行i++。
- 然后从左侧 i 开始扫描，找到大于key 的，r[ i ] 和 r[ j ] 进行交换，并执行 j-- 。
- 重复以上步骤，直到 i = j ;此时一次划分完毕，无序元素集合将分为小于key和大于key的两个无序区。
- 退出循环，说明 i 和 j 指向 key 所在的位置，返回该位置
-
代码实现：
//一次迭代 public int partition(int[] r, int start, int end){ int i = start; int j = end; while(i < j){ //右侧扫描 while(i < j && r[i] <= r[j]){ j--;//一直到r[i] > r[j] ,代表找到了小于key的值，可以进行交换了 } if(i < j){ swap(r, i, j);//交换数组两个元素，此方法省略 i++; } //然后是从左侧扫描 while(i < j && r[i] <= r[j]){ i++; } if(i < j){ swap(r, i, j); j--; } } return i; } //递归实现 public void queickSort(int[] r, int start, int end){ if(end - start > 1){//此时一个区间长度大于1，递归才继续执行，否则结束 int mid = 0; mid = partition(r, start, end); queickSort(r, start, mid);//对左侧无序区进行快速排序，分治处理 queickSort(r, mid+1, end);//对右侧无序区进行快速排序，分治处理 } }
归并排序 （稳定）
归并排序的中心思想还是分治。“归并”的含义就是将两个或者两个以上的有序序列归并成一个有序序列的过程。二路归并排序，是归并排序中最简单的排序方法。
归并排序.jpg
归并排序有个主要问题：如何将两个相邻的有序序列合并成一个有序序列？
因为两个有序序列，在归并过程中，可能会破坏掉原来的序列。像上图中，[20, 60]，[10, 50] 在合并中就会破坏原来的序列了。为此，我们设置i, j, k 三个参数，分别指向两个待归并的序列，以及最终序列的当前位置。也就是 [ i→20 , j→10] ,k指向归并结果存放的位置，一开始是k→20 起始位置。
下面是一次归并的代码
/**
* r[start]→r[mid] , r[mid+1]→r[end]
* 下列start、mid、end 三个参数分别对应有序序列的位置如上
*/
void merge (int[] r, int[] merge, int start, int mid, int end){
int i = start;
int j = mid + 1;
int k = start;
while(i <= mid && j <= end){
merge[k++] = r[i] >= r[j] ? r[j++] : r[i++];//将小的元素放入merge里面
}
if(i <= mid){//第一个子序列没处理完
while(i <= mid){
merge[k++] = r[i++];
}
} else {
while(j <= end){//第二个序列没处理完
merge[k++] = r[j++];
}
}
for (int index = start; index <= end; index++)
r[index] = merge[index];
}
另外要注意的是，使用递归的方式，是先把原来的数组拆分成一个一个的元素，这时候 start>=end ，然后才会开始进行两两归并排序。
//递归实现
void mergeSort(int[] r, int[] merge, int start, int end){
if(start >= end) return;
int mid = (start + end)/2;
mergeSort(r, merge, start, mid);
mergeSort(r, merge, mid+1, end);
merge(r, merge, start, mid, end);
}
待更新。。。
您的点赞鼓励是我的最大动力
我的Android成长日常
