周末憋在家里,复习了一下正则表达式,及常用排序算法,再此小写一篇博文,算是这两日的工作报告了,(~_~)....
常见排序算法(一)→冒泡排序
冒泡排序算法的思想:很简单,每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列从父前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了。因此,复杂度在最坏的情况下是O(N ^ 2)
package com.syc.sort;
import java.util.Arrays;
/**
* 冒泡排序
*
* @author Michael
* @time 9:47:21 PM
* @date Sep 23, 2012
*/
public class BubbleSort {
static int[] num = { 1, 21, 4, 3, 56, 65, 33, 67, 2222, 666 };
public static void main(String[] args) {
Arrays.sort(num);
showArray(num);
}
/**
* From min to max(冒泡排序1)
*/
public static void fromMintoMax1() {
// int[] num = { 1, 21, 4, 3, 56, 65, 33, 67, 2222, 666 };
for (int i = 0, len = num.length; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (num[i] > num[j]) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
/**
* From min to max(冒泡排序2,已优化)
*/
public static void fromMintoMax2() {
for (int i = 0, len = num.length; i < len; i++) {
int k = i;
for (int j = k + 1; j < len; j++) {
if (num[j] < num[k]) {
k = j;
}
}
if (k != i) {
int temp = num[k];
num[k] = num[i];
num[i] = temp;
}
}
showArray(num);
}
/**
* From min to max(冒泡排序3,已优化,效率较前两种高)
*/
public static void fromMintoMax3() {
int k, temp;
for (int i = 0, len = num.length; i < len; i++) {
k = i;
for (int j = k + 1; j < len; j++) {
if (num[j] < num[k]) {
k = j;
}
}
if (k != i) {
temp = num[k];
num[k] = num[i];
num[i] = temp;
}
}
showArray(num);
}
/**
* From mxx to min(冒泡排序1)
*/
public static void fromMaxtoMin1() {
for (int i = 0, len = num.length; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (num[i] < num[j]) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
showArray(num);
}
/**
* From mxx to min(冒泡排序2,已优化,)
*/
public static void fromMaxtoMin2() {
for (int i = 0, len = num.length; i < len; i++) {
int k = i;
for (int j = k + 1; j < len; j++) {
if (num[j] > num[k]) {
k = j;
}
}
if (k != i) {
int temp = num[k];
num[k] = num[i];
num[i] = temp;
}
}
showArray(num);
}
/**
*
* @param array
*/
public static void showArray(int[] array) {
for (int arr : array) {
System.out.print(arr + " ");
}
System.out.println("");
}
}
常见排序算法(二)→插入排序
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是:
1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。
最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。
最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。
插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。
因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
Java实现:
package com.syc.sort;
/**
*
* @author Michael
* @time 9:17:30 PM
* @date Sep 23, 2012
*/
public class InsertSort {
/**
*
* @param array
*/
public static void showArray(int[] array) {
for (int arr : array) {
System.out.print(arr + " ");
}
System.out.println("");
}
/**
*
* @param array
*/
public static void insertSort(int[] array) {
int index;
for (int i = 1; i < array.length; i++) {
int currentData = array[i];
for (index = i; (index > 0) && (currentData < array[index - 1]); index--) {
array[index] = array[index - 1];
}
array[index] = currentData;
showArray(array);
}
}
public static void main(String[] args) {
int[] array = { 9, 2, 7, 3 };
insertSort(array);
}
}
---------------
分享到:
相关推荐
压缩包含有板式家具下料算法代码及生成好的exe文件,算法可能不是最好的,仅供交流学习使用,有什么问题大家可以提出来互相讨论
自己用Unity5.2.3写的一个小游戏——拼图,内含所有的代码及场景文件
本压缩包里是用vs2013写的利用遗传算法求解最短路径问题,本人根据查找到的相应资源进行了改进,解决了一些bug,使得该程序利用起来更加方便、实用。
压缩包里是用vs2013编写的利用模拟退火算法求解TSP问题,本人根据查找到的相应资源进行了改进,解决了一些bug,并修改了相应的代码,使得该程序二次开发利用起来更加方便、实用。
四川省雨城区高一下学期语文3月月考试卷.pdf
2019年四川省雅安市雨城区考核招聘模拟试题及答案解析.docx
初中化学-四川省雅安市雨城区中里镇中学九年级化学金属材料习题精选.doc.pdf
四川省雅安市雨城区 八年级物理12月月考试题(无答案) 新人教版 试题.doc
四川省雅安市雨城区 八年级数学12月月考试题(无答案) 新人教版 试题.doc
初中化学-四川省雅安市雨城区中里镇中学九年级化学金属材料习题精选.doc-.pdf
四川省雅安市雨城区中里镇中学九年级化学《金属材料》课件4(人教版).ppt
四川省雅安市雨城区中里镇中学九年级化学《化学肥料2》课件(人教版).ppt
四川省雅安市雨城区 八年级英语12月月考试题(无答案) 人教新目标版 试题.doc
四川省雅安市雨城区中里镇中学九年级化学《金属的化学性质》课件5(人教版).ppt
四川省雅安市雨城区2020学年八年级英语12月月考试题(无答案) 人教新目标版.doc
四川省雅安市雨城区中里镇中学九年级化学《常见的酸和碱》课件4(人教版).ppt
四川省雅安市雨城区中里镇中学九年级化学《化学元素与人体健康》课件1(人教版).ppt
四川省雅安市2020-2021学年高一下学期期末检测地理试题 .zip
Windows系统编程——注册表编程试验报告
四川省雅安市2019-2020学年高二地理上学期期末检测试题(PDF)答案