基本算法分類結構
基本排序算法.png
參考鏈接
http://www.cnblogs.com/0201zcr/p/4764427.html
http://www.cnblogs.com/qqzy168/archive/2013/08/03/3219201.html
交換排序—冒泡排序
描述：
在排序數(shù)組Arrys中迫肖，對當前還未排好順序的全部輸，自上而下對相鄰兩數(shù)進行比較和調整卧须。讓較大的數(shù)往下沉壮吩，較小往下沉获搏。即：發(fā)現(xiàn)相鄰比較數(shù)順序不符合排序要求始锚，交換位置剖笙。
步驟：
比較相鄰的元素未妹。如果第一個比第二個大，就交換他們兩個夸赫。
1.遍歷數(shù)組起始位i，i到arrys.length-1
2.再次遍歷數(shù)組咖城，j位置到arrys.length-1-i
3.條件判斷茬腿，交換位置操作
/**
* 冒泡升序
* 對每一對相鄰元素作同樣的工作呼奢，從開始第一對到結尾的最后一對。在這一點切平，最后的元素應該會是最大的數(shù)握础。
* 針對所有的元素重復以上的步驟，除了最后一個悴品。
* 持續(xù)每次對越來越少的元素重復上面的步驟禀综，直到?jīng)]有任何一對數(shù)字需要比較。
* @param arrys
* @return
*/
public Integer[] bubbleSortByAsc(Integer[] arrys){
Integer[] clone = arrys.clone();
for(int i=0;i<clone.length-1;i++){
for(int j=0;j<clone.length-1-i;j++){
if(clone[j]>clone[j+1]){
int temp=clone[j];
clone[j]=clone[j+1];
clone[j+1]=temp;
}
}
}
return clone;
}
/**
* 冒泡降序
* @param arrys
* @return
*/
public Integer[] bubbleSortByDesc(Integer[] arrys){
Integer[] clone = arrys.clone();
for(int i=0;i<clone.length-1;i++){
for(int j=0;j<clone.length-1-i;j++){
if(clone[j]>clone[j+1]){
int temp=clone[j];
clone[j]=clone[j+1];
clone[j+1]=temp;
}
}
}
return clone;
}
交換排序—快速排序
描述：
選擇一個基準元素苔严，通常以第一個或最后一個定枷，通過一趟排序，將待排序列分成兩部分届氢。一部分比基準元素小欠窒，另一部分比基準元素大或相等
/**
* 快速排序升序
*
* @param nums src
* @return result
*/
public Integer[] quickSortByAsc(Integer[] nums) {
Integer[] clone = nums.clone();
System.out.println("quick sort by Asc");
quickSortByAsc(clone, 0, clone.length - 1);
return clone;
}
public void quickSortByAsc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = getMiddleAsc(nums, low, high);
quickSortByAsc(nums, low, middle - 1);
quickSortByAsc(nums, middle + 1, high);
}
}
/**
* 獲取中軸位置(Asc升序)
*
* @param nums src
* @param low low
* @param high high
* @return position
*/
private int getMiddleAsc(Integer[] nums, int low, int high) {
int middleNum = nums[low];//取第一次傳入的low位位中軸數(shù)
while (low < high) {
while (low < high && nums[high] >= middleNum) {//右邊high游標不斷前移，如果當前位置的數(shù)大于中軸上的數(shù)
high--;
}
nums[low] = nums[high];//小的移到左邊
while (low < high && nums[low] <= middleNum) {//左邊low游標不斷后移退子，如果當前l(fā)ow位置的數(shù)小于中軸上的數(shù)
low++;
}
nums[high] = nums[low];//大的移到右邊
}
nums[low] = middleNum;//將中軸數(shù)放到正確的位置上
return low;
}
/**
* 快速排序降序
*
* @param nums src
* @return result
*/
public Integer[] quickSortByDesc(Integer[] nums) {
Integer[] clone = nums.clone();
System.out.println("quick sort by desc:");
quickSortByDesc(clone, 0, clone.length - 1);
return clone;
}
private void quickSortByDesc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = getMiddleDesc(nums, low, high);
quickSortByDesc(nums, low, middle - 1);//對中軸左邊繼續(xù)排序
quickSortByDesc(nums, middle + 1, high);//對中軸右邊繼續(xù)排序
}
}
/**
* 獲取中軸位置(Desc降序)
*
* @param nums src
* @param low low
* @param high high
* @return position
*/
private int getMiddleDesc(Integer[] nums, int low, int high) {
int middleNum = nums[low];//取第一次傳入的low位位中軸數(shù)
while (low < high) {
while (low < high && nums[high] <= middleNum) {//右邊high游標不斷前移岖妄，如果當前位置的數(shù)小于中軸上的數(shù)
high--;
}
nums[low] = nums[high];//大的數(shù)移到左邊
while (low < high && nums[low] >= middleNum) {//左邊low游標不斷后移，如果當前l(fā)ow位置的數(shù)大于中軸上的數(shù)
low++;
}
nums[high] = nums[low];//小的數(shù)移到右邊
}
nums[low] = middleNum;//將中軸數(shù)放到正確的位置上
return low;
}
插入排序——直接插入排序
描述：
在排序的數(shù)組中寂祥，假設前面n-1（n>=2）個數(shù)已經(jīng)排好順序荐虐，現(xiàn)在將第n個數(shù)插入到前面的有序數(shù)組中，使得這n個數(shù)也是排好順序丸凭。反復循環(huán)缚俏。直到排列完成。
/**
* 基本思想：每步將一個待排序的記錄贮乳，按其順序碼大小插入到
* 前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后）忧换，
* 直到全部插入排序完為止。
*
* 從第一個元素開始向拆，該元素可以認為已經(jīng)被排序
* 取出下一個元素亚茬，在已經(jīng)排序的元素序列中從后向前掃描
* 如果該元素（已排序）大于新元素，將該元素移到下一位置
* 重復步驟3浓恳，直到找到已排序的元素小于或者等于新元素的位置
* 將新元素插入到該位置中
* 重復步驟2
* @param nums
*/
public Integer[] insertSortByAsc(Integer[] nums){
System.out.println("insert sort by Asc:");
Integer[] clone = nums.clone();
for(int i=0;i<clone.length;i++){
int temp=clone[i];//取出下個待插入排序的數(shù)
int j=0;//插入的位置標記
for(j=i;j>0&&temp<clone[j-1];j--){//滿足待排序數(shù)小于前面的數(shù)條件刹缝，j--
clone[j]=clone[j-1];//整體后移一位
}
clone[j]=temp;
}
return clone;
}
/**
* 基本思想：每步將一個待排序的記錄，按其順序碼大小插入到
* 前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后）颈将，
* 直到全部插入排序完為止梢夯。
*
* 從第一個元素開始，該元素可以認為已經(jīng)被降序排序
* 取出下一個元素晴圾，在已經(jīng)排序的元素序列中從后向前掃描
* 如果該元素（已排序）小于新元素颂砸，將該元素移到下一位置
* 重復步驟3，直到找到已排序的元素大于或者等于新元素的位置
* 將新元素插入到該位置中
* 重復步驟2
* @param nums
*/
public Integer[] insertSortByDesc(Integer[] nums){
System.out.println("insert sort by Desc:");
Integer[] clone = nums.clone();
for(int i=0;i<clone.length;i++){
int temp=clone[i];//取出下個待插入排序的數(shù)
int j=0;//插入的位置標記
for(j=i;j>0&&temp>clone[j-1];j--){//滿足待排序數(shù)大于前面的數(shù)條件，j--
clone[j]=clone[j-1];//整體后移一位
}
clone[j]=temp;
}
return clone;
}
插入排序——希爾排序
描述：將要排序的一組數(shù)按某個增量 d（n/2,n為要排序數(shù)的個數(shù)）分成若干組人乓，每組中記錄的下標相差 d.對每組中全部元素進行直接插入排序勤篮，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序色罚。當增量減到 1 時碰缔，進行直接插入排序后，排序完成戳护。
/**
* 希爾排序升序
* 基本思想：
* 將數(shù)組拆分成d長度的小數(shù)組金抡，最開始d長度為length/2
* 對小數(shù)組插入排序
* 再將d長度縮小為d/2
* 重復操作，直到d=1
* @param nums src numbers
* @return result numbers
*/
public Integer[] shellSortAsc(Integer[] nums) {
System.out.println("shell sort by Asc:");
Integer[] clone = nums.clone();
for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次縮小二分之一
for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d長度的段
//對d長度的每組數(shù)進行插入排序,每組起始坐標為groupStarPosition
for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
int temp = clone[j];
int k = 0;
for (k = j; k > groupStarPosition && temp < clone[k - 1]; k--) {
clone[k] = clone[k - 1];
}
clone[k] = temp;
}
}
}
return clone;
}
/**
* 希爾排序升序
* 基本思想：
* 將數(shù)組拆分成d長度的小數(shù)組腌且，最開始d長度為length/2
* 對小數(shù)組插入排序
* 再將d長度縮小為d/2
* 重復操作梗肝，直到d=1
* @param nums src numbers
* @return result numbers
*/
public Integer[] shellSortByDesc(Integer[] nums) {
System.out.println("shell sort by Desc:");
Integer[] clone = nums.clone();
for (int d = clone.length / 2; d >= 1; d /= 2) {//d每次縮小二分之一
for (int groupStarPosition = 0; groupStarPosition <= clone.length - d; groupStarPosition ++) {//分成d長度的段
//對d長度的每組數(shù)進行插入排序,每組起始坐標為groupStarPosition
for (int j = groupStarPosition; j < groupStarPosition+d; j++) {
int temp = clone[j];
int k = 0;
for (k = j; k > groupStarPosition && temp > clone[k - 1]; k--) {
clone[k] = clone[k - 1];
}
clone[k] = temp;
}
}
}
return clone;
}
選擇排序——直接選擇排序
描述：排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換切蟋；
然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換统捶，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。
/**
* 選擇排序（升序）
* 每次選擇一個最小值排在有序數(shù)組的后面一位上
* 主要關心每次選擇的最小值的位置與值柄粹，再將此位置與數(shù)值交換
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] selectSortByAsc(Integer[] nums) {
System.out.println("select sort by Asc:");
Integer[] clone = nums.clone();
int position = 0;//記錄本次選擇數(shù)的數(shù)組位置
int value = 0;//記錄本次選擇的值
for (int i = 0; i < clone.length; i++) {
value = clone[i];//初始值為clone[i]
for (int j = i; j < clone.length; j++) {
//如果發(fā)現(xiàn)有值比當前選擇的值小喘鸟，position記錄他在數(shù)組中的位置，更新value的值驻右，進行下次比較
if (clone[j] <= value) {
position = j;
value = clone[j];
}
}
//將此次選擇的最小值與clone[i]位置交換
int temp = clone[i];
clone[i] = value;
clone[position] = temp;
}
return clone;
}
/**
* 選擇排序(降序)
* 每次選擇一個最大值排在有序數(shù)組的后面一位上
* 主要關心每次選擇的最大值的位置與值什黑，再將此位置與起始選擇位置交換
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] selectSortByDesc(Integer[] nums) {
System.out.println("select sort by Desc:");
Integer[] clone = nums.clone();
int position = 0;//記錄本次選擇數(shù)的數(shù)組位置
int value = 0;//記錄本次選擇的值
for (int i = 0; i < clone.length; i++) {
value = clone[i];//初始值為clone[i]
for (int j = i; j < clone.length; j++) {
//如果發(fā)現(xiàn)有值比當前選擇的值大，position記錄他在數(shù)組中的位置堪夭，更新value的值愕把，進行下次比較
if (clone[j] >= value) {
position = j;
value = clone[j];
}
}
//將此次選擇的最小值與clone[i]位置交換
int temp = clone[i];
clone[i] = value;
clone[position] = temp;
}
return clone;
}
選擇排序——堆排序(待續(xù))
歸并排序
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列森爽，每個子序列是有序的恨豁。然后再把有序子序列合并為整體有序序列。
/**
* 歸并排序升序
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] mergeSortAsc(Integer[] nums) {
System.out.println("merge sort By Asc:");
Integer[] clone = nums.clone();
mergeSortAsc(clone, 0, clone.length - 1);
return clone;
}
/**
* low 到high 元素歸并
*
* @param nums src numbers
* @param low 歸并元素起始位置
* @param high 歸并元素結束位置
*/
public void mergeSortAsc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
mergeSortAsc(nums, low, middle);//對左邊歸并排序
mergeSortAsc(nums, middle + 1, high);//對右邊歸并排序
mergeAsc(nums, low, middle, high);//歸并
}
}
/**
* 歸并操作爬迟，將有序的兩邊的子序列合并成整體有序的數(shù)
*
* @param nums 待排序數(shù)組
* @param low 待排的開始位置
* @param middle 待排中間位置
* @param high 待排結束位置
*/
public void mergeAsc(Integer[] nums, int low, int middle, int high) {
//輔助數(shù)組橘蜜，用于存儲新排序好的數(shù)組
Integer[] temp = new Integer[high - low + 1];
//左指針
int left = low;
//右指針
int right = middle + 1;
//輔助數(shù)組的標記
int k = 0;
// 把較小的數(shù)先移到新數(shù)組中
while (left <= middle && right <= high) {
if (nums[left] < nums[right]) {
temp[k] = nums[left];
left++;
k++;
} else {
temp[k] = nums[right];
right++;
k++;
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (left <= middle) {
temp[k++] = nums[left++];
}
// 把右邊剩余的數(shù)移入數(shù)組
while (right <= high) {
temp[k++] = nums[right++];
}
// 把新數(shù)組中的數(shù)覆蓋回到nums數(shù)組
for (int i = 0; i < temp.length; i++) {
nums[low + i] = temp[i];
}
}
/**
* 歸并排序（降序）
*
* @param nums src numbers
* @return result numbers
*/
public Integer[] mergeSortDesc(Integer[] nums) {
System.out.println("merge sort by Desc:");
Integer[] clone = nums.clone();
mergeSortDesc(clone, 0, clone.length - 1);
return clone;
}
/**
* low 到high 元素desc歸并
*
* @param nums src numbers
* @param low 歸并元素起始位置
* @param high 歸并元素結束位置
*/
public void mergeSortDesc(Integer[] nums, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
mergeSortDesc(nums, low, middle);
mergeSortDesc(nums, middle + 1, high);
mergeDesc(nums, low, middle, high);
}
}
/**
* 歸并操作，將有序的兩邊的子序列合并成整體有序的數(shù)
*
* @param nums 待排序數(shù)組
* @param low 待排的開始位置
* @param middle 待排中間位置
* @param high 待排結束位置
*/
public void mergeDesc(Integer[] nums, int low, int middle, int high) {
//輔助數(shù)組付呕，用于存儲新排序好的數(shù)組
Integer[] temp = new Integer[high - low + 1];
//左指針
int left = low;
//右指針
int right = middle + 1;
//輔助數(shù)組的標記
int k = 0;
// 把較大的數(shù)先移到新數(shù)組中
while (left <= middle && right <= high) {
if (nums[left] > nums[right]) {
temp[k] = nums[left];
left++;
k++;
} else {
temp[k] = nums[right];
right++;
k++;
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (left <= middle) {
temp[k++] = nums[left++];
}
// 把右邊剩余的數(shù)移入數(shù)組
while (right <= high) {
temp[k++] = nums[right++];
}
// 把新數(shù)組中的數(shù)覆蓋回到nums數(shù)組
for (int i = 0; i < temp.length; i++) {
nums[low + i] = temp[i];
}
}
