簡單排序
這裡的簡單排序分為三種：冒泡排序，選擇排序、直接插入排序
下面先給出生成數組的類：
生成資料
package per.lihao.sort;
import java.util.Random;
/**
* Author: LiHao
* Time: 2018/12/5 10:09
*/
public class SortSequence {
private int MAXSIZE = 10;
private int[] mem = new int[MAXSIZE];
/**
* 給一數組資料構造
* @param array
*/
public SortSequence(int... array){
if(array.length>MAXSIZE){
System.out.println("輸入參數大于最大長度，自動擴增...");
MAXSIZE = array.length;
mem = new int[MAXSIZE];
}
for (int i =0;i<MAXSIZE;i++){
mem[i] = array[i];
}
}
/**
* 最大長度構造
* @param maxlength
*/
public SortSequence(int maxlength){
MAXSIZE = maxlength;
mem = new int[MAXSIZE];
Random random = new Random();
for (int i=0;i<MAXSIZE;i++){
mem[i] = random.nextInt(200);
}
}
/**
* 無參構造
*/
public SortSequence(){
Random random = new Random();
for (int i=0;i<MAXSIZE;i++){
mem[i] = random.nextInt(200);
}
}
/**
* 擷取資料
* @return
*/
public int[] getMem(){
return mem;
}
/**
* 列印原始資料
*/
public void printMem(){
for (int i=0;i<MAXSIZE;i++){
System.out.print(mem[i]+" ");
}
System.out.println();
}
}
以下排序均預設為逆序
冒泡排序
流程：冒泡排序是交換排序的一種，他是從尾部開始周遊，兩兩資料之間進行比較，若前者小于後者，則交換，這樣最大的資料就會不斷的往前，直到達到首部。不斷的重複，則資料就會進行排序。
package per.lihao.sort.simplesort;
import per.lihao.sort.SortSequence;
/**
* 冒泡排序
* 交換排序之一
* 時間複雜度是O（n^2）
* Author: LiHao
* Time: 2018/12/5 10:07
*/
public class BubbleSort {
public static void printArray(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
/**
* 最簡單的版本
* 從上到下依次循環
* 若遇到比目前指針所指資料大（小）的資料，直接交換
* 直到沒有比目前指針資料大（小）的資料時，指針往下走
* 結束循環
* 分析：該方法較為低效；票好序的序列對未排序的序列無幫助
* @param array
* @param reverse
* @return
*/
public static int[] sort_one(int[] array,boolean reverse){
int[] result = array.clone();
for(int i=0;i<result.length-1;i++){
for (int j=i+1;j<result.length;j++){
if (reverse){
if (result[j]>result[i]){
int t = result[j];
result[j] = result[i];
result[i] = t;
}
}else {
if (result[j]<result[i]){
int t = result[j];
result[j] = result[i];
result[i] = t;
}
}
}
}
return result;
}
/**
* 修改後的版本
* 進行兩兩比較，将較大（小）的一方不斷地往上排 --- 标準的冒泡排序
* 效率會比第一種高一些
* @param array
* @return
*/
public static int[] sort_two(int[] array,boolean reverse){
int[] result = array.clone();
for (int i=0;i<result.length;i++){
for (int j=result.length-1;j>i;j--){
if (reverse){
if(result[j]>result[j-1]){
int t = result[j];
result[j] = result[j-1];
result[j-1] = t;
}
}
else {
if(result[j]<result[j-1]){
int t = result[j];
result[j] = result[j-1];
result[j-1] = t;
}
}
}
}
return result;
}
/**
* 加入了對子序列是否為沒有被排序的判斷
* 若上次循環已經判斷子序列排序notsorted為false，這說明該子序列已經有序，不用再進行比較了
* @param array
* @param reverse
* @return
*/
public static int[] sort_three(int[] array,boolean reverse){
int[] result = array.clone();
boolean notsorted = true;
for (int i=0;(i<result.length) && notsorted;i++){
notsorted = false;
for (int j=result.length-1;j>i;j--){
if (reverse){
if(result[j]>result[j-1]){
int t = result[j];
result[j] = result[j-1];
result[j-1] = t;
notsorted = true;
}
}
else {
if(result[j]<result[j-1]){
int t = result[j];
result[j] = result[j-1];
result[j-1] = t;
notsorted = true;
}
}
}
}
return result;
}
public static void main(String[] args) {
SortSequence ss = new SortSequence(82,195,19,108,153,39,120,125,136,181);
ss.printMem();
System.out.println("****************************");
int[] a = BubbleSort.sort_two(ss.getMem(),false);
BubbleSort.printArray(a);
}
}
簡單選擇排序
選擇排序的一種
流程：指針指定到第i個位置(i=0)，并與其後的所有資料進行比較，選出最大的那一個進行交換。循環繼續，i+1，則每個位置上都會選取第i個大的資料，最終完成排序。
package per.lihao.sort.simplesort;
import per.lihao.sort.SortSequence;
/**
* 選擇排序
* 優點是：無需那麼多次資料的移動，時間效率為：O(n^2)
* Author: LiHao
* Time: 2018/12/5 13:54
*/
public class SelectSort {
public static int[] sort(int[] array,boolean reverse){
int[] result = array.clone();
int cursor,cvalue;
for (int i=0;i<result.length;i++){
cursor = i;
cvalue = result[i];
for (int j=i;j<result.length;j++){
if (reverse){
if(result[j]>cvalue){
cvalue = result[j];
cursor = j;
}
}else {
if(result[j]<cvalue){
cvalue = result[j];
cursor = j;
}
}
}
if(cursor!=i){
int t = result[cursor];
result[cursor] = result[i];
result[i] = t;
}
}
return result;
}
public static void main(String[] args) {
SortSequence ss = new SortSequence(82,195,19,108,153,39,120,125,136,181);
ss.printMem();
System.out.println("****************************");
int[] a = SelectSort.sort(ss.getMem(),false);
BubbleSort.printArray(a);
}
}
直接插入排序
流程：循環選取i=1之後的資料，每次插入時預設前面的序列是有序的，找到目前資料插入的位置（從尾部依次該位置前的資料比較，找到大于該值的索引x，則x+1後的的資料每個都需要往後移動一位，再将該值賦給x+1索引處），最終完成排序。
package per.lihao.sort.simplesort;
import per.lihao.sort.SortSequence;
/**
* 直接插入排序
* 時間複雜度 O(n^2)
* Author: LiHao
* Time: 2018/12/5 14:11
*/
public class InsertSort {
public static int[] sort(int[] array,boolean reverse){
int[] result = array.clone();
for (int i = 1;i<result.length;i++){
if (reverse){
if(result[i]>result[i-1]){
int j=i;
int temp = result[i];
while (j>0 && result[j-1]<temp){
result[j] = result[j-1];
j--;
}
result[j] = temp;
}
}else {
if(result[i]<result[i-1]){
int j=i;
int temp = result[i];
while (j>0 && result[j-1]>temp){
result[j] = result[j-1];
j--;
}
result[j] = temp;
}
}
}
return result;
}
public static void main(String[] args) {
SortSequence ss = new SortSequence(82,195,19,108,153,39,120,125,136,181);
ss.printMem();
System.out.println("****************************");
int[] a = InsertSort.sort(ss.getMem(),false);
BubbleSort.printArray(a);
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)