排序算法：就是对数组继续从小到大按顺序的排列
排序算法有如下：
1）冒泡排序：通过相邻的两个数据进行比较，然后排序 O(n^2)
2）选择排序：每一步中选取最小值来从新排序 O(n^2)
3）插入排序：前两个进行比较排序，将第三个与前面已经排序好的进行比较，放到合适位置 O(n^2)
4）Shell排序：插入排序的增强版，第一次增量为n/2（增量为每组元素个数），分成2个组，每组进行比较；
然后缩小增量为n/4，分成4个组，每组进行比较 ，直到增量为1，最后插入排序 O(n^3/2)
5）快速排序：通过分界值，左边小于，右边大于。。 O(nlogn)
6）堆排序：二叉树 O(nlogn)
- 冒泡排序
/**
* Created by malei on 2016/12/4.
* 冒泡排序：通过相邻的两个数据进行比较，然后排序 O(n^2)
* 1)依次比较相邻的两个元素的大小
* 2）如果前面的数据大，就交换。经过一轮多次的比较，便可将最大的数找到位置
* 3）然后进行n-1轮
*/
public class a_冒泡排序 {
public static void main(String[] args){
int[] arr = {190,234,45,78,100};
bubbleSort(arr);
}
private static void bubbleSort(int[] arr) {
int length = arr.length;
int temp=0;
for(int i = 1; i < length; i++){
for (int j = 0; j < length - i; j++){ //每一次都可以确定最大的值
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
Log.show("第"+i+"次："+Arrays.toString(arr));
}
Log.show(Arrays.toString(arr));
}
}
- 选择排序
/**
* Created by malei on 2016/12/4.
* 选择排序：每一步中选取最小值来从新排序 O(n^2)
* 1）从数组中找到最小的数据，将其和第1个位置的数据交换
* 2）接着从剩下的n-1个元素中选择次小的元素，将其和第2个位置的数据交换
* 3）然后不断重复，执行n-1次
*/
public class b_选择排序 {
public static void main(String[] args){
int[] arr = {190,234,45,78,100};
selectSort(arr);
}
private static void selectSort(int[] arr) {
int length = arr.length;
int temp=0;
Log.show("原生数据："+ Arrays.toString(arr));
for (int i = 0; i < length-1 ;i++){
for (int j = i+1;j < length;j++){
if(arr[i] > arr[j]){
temp = arr[i];
arr[i] = arr[j];
arr[j] =temp;
}
}
Log.show("第"+i+"次："+Arrays.toString(arr));
}
Log.show(Arrays.toString(arr));
}
}
- 插入排序：
/**
* Created by malei on 2016/12/4.
* 插入排序：前两个进行比较排序，将第三个与前面已经排序好的进行比较，放到合适位置 O(n^2)
* 1)首先对数组前2个数据进行从小到大的排序
* 2）接着将第3个数据与排好序的2个数据比较，将第3个数据插入到合适的位置
* 3）然后，将第4个元素插入到已排好序的前3个数据中
*/
public class c_插入排序 {
public static void main(String[] args){
int[] arr = {190,234,45,78,100};
insertSort(arr);
}
private static void insertSort(int[] arr) {
int length = arr.length;
int temp,j=0;
Log.show("原生数据："+ Arrays.toString(arr));
for (int i =1;i < length; i++){
temp = arr[i]; //将后一位保存
j = i-1;
while (j >= 0 && temp < arr[j]){ //前一位大于后一位
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
Log.show("第"+i+"次："+Arrays.toString(arr));
}
Log.show(Arrays.toString(arr));
}
}
- Shell排序
**
* Created by malei on 2016/12/4.
*/
public class d_Shell排序 {
public static void main(String[] args){
int[] arr = {190,234,45,78,100};
shellSort2(arr);
}
private static void shellSort(int[] arr) {
int length = arr.length;
int temp=0;
int j,x=0;
Log.show("原生数据："+ Arrays.toString(arr));
for (int r = length/2 ; r >= 1 ; r =r/2){ //r是增量，每次都缩小增量。增量为每组的元素个数
for (int i = r; i<length; i++){
temp = arr[i];
j = i-r; //
while (j>=0 && temp < arr[j]){
arr[j+r] = arr[j];
j = j-r; //进行下一组的比较
}
arr[j+r] = temp;
}
x++;
Log.show("第"+x+"次排序"+Arrays.toString(arr));
}
Log.show(Arrays.toString(arr));
}
private static void shellSort2(int[] arr) {
int length = arr.length;
int temp ,j= 0;
int d = length/2 ; //增量
Log.show("原生数据："+ Arrays.toString(arr));
while (d >= 1){ //循环到增量为1时结束
for (int i = d; i<length; i++){
temp = arr[i]; //获取序列中的下一个数据
j = i -d; //序列中前一个数据的序号
while (j >= 0 && arr[j] >temp){ //前一个数大于下一个数
arr[j+d] = arr[j]; //将后一个数向前移动
j = j-d; //修改序号，继续向前比较
}
arr[j+d] = temp; //保存数据
}
d= d/2; //增量减小
}
Log.show(Arrays.toString(arr));
}
}
网友评论