排序算法
- 冒泡(Bubble)
- 选择
- 插入
- 归并
- 快速
- 计数排序
冒泡排序
简单的说就是，每一次遍历都把最大(小)的通过比较选出来。
- 从第一个元素开始比较相邻的两个元素，把大（小）的往后移；
- 比较到未排序的最后一个元素时，会得出这趟冒泡得到的最大（小）元素；
- 一直遍历到只有一个元素
代码实现：
(java)
int []a = {5,4,3,2,1,12,32,13,24,53};
for (int i = a.length - 1 ; i >0; i--){
for (int j = 0;j< i;j++){
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
选择排序
这个算法也很简单，每次都把未排序序列里最小（大）的选出来，放在序列。
- 一趟遍历未排序序列，选出最小（大）的数字；
- 把这个数字放在未排序序列前面，*未排序序列 + 1
- 重复步骤到完成排序。
代码实现：
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 0; i<a.length;i++){
int min = a[i];
int mark = i;
for(int j = i ;j <a.length ; j++){
if( min > a[j])
{
min = a[j];
mark = j;
}
}
int temp = a[i];
a[i] = min;
a[mark] = temp;
}
插入排序
排序流程：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2~5
实现代码：
package Sort;
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
for (int i = 1;i<a.length;i++){
int temp = a[i];
for (int j = i - 1 ; j>=0 ; j--){
if(temp < a[j]){
a[j+1] = a[j];
a[j] = temp;
}else{
break;
}
}
}
for (int i = 0 ; i< a.length ; i++)
System.out.print(a[i]+" ");
}
}
归并排序
归并排序采用呢，采用了分治法来让两个数组归并。
排序流程：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤 3 直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
sort(nums, low, mid);
// 右边
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []a = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
MergeSort.sort(a, 0, a.length-1);
for (int i = 0 ; i< a.length ; i++)
System.out.print(a[i]+" ");
}
