插入排序：
核心：逐个取出元素，遍历之前已经排序好的数据集合，逐个比较，插入元素
算法实现：
public class InsertSort{ public static> void insertSort(T[] a){
for(int p = 1; p < a.length; p++)
{
T tmp = a[p];//保存当前位置p的元素，其中[0,p-1]已经有序
int j;
for(j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--)
{
a[j] = a[j-1];//后移一位
}
a[j] = tmp;//插入到合适的位置
}
}
//for test purpose
public static void main(String[] args) {
Integer[] arr = {34,8,64,51,32,21};
insertSort(arr);
for (Integer i : arr) {
System.out.print(i + " ");
}
}
}
选着排序：
核心：逐个遍历，从未排序的集合中选着最值（最大，最小），插入另外一个集合中
算法实现：
//选择排序
public class SelectionSort {
public static void main(String[] args) {
int[] arr={1,3,2,45,65,33,12};
System.out.println("交换之前：");
for(int num:arr){
System.out.print(num+" ");
}
//选择排序的优化
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("交换后：");
for(int num:arr){
System.out.print(num+" ");
}
}
}
冒泡排序：
核心：假如有几个数字int score[] = {67, 69, 75, 88}; 按照从大到小排序。
有2种思路，第一种，score[j] 和 score[j+1] 比较 如果 前者比后者小，把前者和后者调换顺序，两两调换后一轮下来 最小的会被排到最后去。每一轮j都从0开始，当i轮排序，就有最后面的i个数字因为他是最小的，所以后面的每轮都不用理他了，也就是 score.length-1-i 往后的数不用管了，如上，第一轮有4个数字 i为0 ，那么score.length-1-i 为3，也就是下标是3以后的可以不用管，3往后没有数字，所以第一轮所有的数字都要参加比较，第二轮I=1 score.length-1-i 为2 也就是说 下标2后面的 下标为3的数字不用比了，因为两两比较厚，67会到 score[3]
算法实现：
for(int i =0;i < score.length - 1;i++)
{
for(int j = 0;j < score.length - 1-i;j++)// j开始等于0，
{
if(score[j] < score[j+1])
{
int temp = score[j];
score[j] = score[j+1];
score[j+1] = temp;
}
}
}
快速排序：
核心：是对冒泡排序的一种改进，基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
算法实现：
int PartSort(int* array,int left,int right)
{
int& key = array[right];
while(left < right)
{
while(left < right && array[left] <= key)
{
++left;
}
while(left < right && array[right] >= key)
{
--right;
}
swap(array[left],array[right]);
}
swap(array[left],key);
return left;
}
网友评论