692
技術社區[雲棲]
算法之簡單排序
一。直接插入排序1。直接插入排序：直接插入排序是一種簡單的排序方法，它的基本思想是將待排序的記錄按照其值的大小插入到已排好序的有序表的適當位置，直到全部插入完為止。舉個整型的排序例子
2。直接插入排序的偽代碼：
insertionsort(data[]) for i=1 to data.length-1 tmp=data[i]; 將所有大於tmp的元素data[j]向後移動一位; 將tmp放在正確的位置上;
3.簡單例子，以整型為例。
A）ruby語言實現：
def insertion_sort(a) i=1 while i<a.length tmp=a[i] j=i while j>0 break if tmp>a[j-1] a[j]=a[j-1] j-=1 end a[j]=tmp i+=1 endend a=[10,2,3]insertion_sort(a)a.each{|i | print i.to_s+" "}
B）java語言實現：
package com.sohu.blog.denns_zane.sort;
public class InsertSort
{
public static void main(String args[]){ int []data={12,2,3,56,90};
insertsort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" ");
} } public static void insertsort(int []data){ for(int i=1,j;i<data.length;i++){ int tmp=data[i]; for(j=i;j>0&&tmp<data[j-1];j--) data[j]=data[j-1]; data[j]=tmp; } }
}
5。算法複雜度：
最好情況：進行n-1次比較和2(n-1)次移動，盡管他們其實都是多餘的，複雜度O(n)
最壞情況：具體計算略，O(n*n)
平均情況：O(n*n)，也就是接近最壞情況，在平均情況下，數組大小翻倍，它的排序工作將是原來的4倍。
二。選擇排序
1。算法描述：選擇算法試圖先查找一個放錯位置的元素並將它放到最終位置上，以此來局部化數組元素的交換。選擇值最小的元素並將它和第一個位置上的元素交換。在第i步中，查找data[i],...,data[n-1]中的最小元素，並將它和data[i]進行交換。重複此過程，直到所有的元素都放入正確的位置為止。
2。偽代碼描述：
selectionsort(data[]) for i=0 to data.length-2 從data[i],,data[n-1]中選取最小的元素 將它和data[i]交換
3。實現，以整型數組為例：
1)ruby語言實現：
def selection_sort(a) least=0 for i in (0..(a.length-2)) j=i+1 least=i while j<a.length if a[j]<a[least] least=j end j+=1 end a[least],a[i]=a[i],a[least] unless least==i #交換 endenda=[12,4,34,23,45,35]selection_sort(a)a.each{|i| print i.to_s+" "}
代碼很好理解，不做解釋。
2）java語言實現：
package com.sohu.blog.denns_zane.sort;public class SelectionSort{ public static int[] selection_sort(int [] data){ int i,j,least=0; for(i=0;i<data.length-1;i++){ for(j=i+1,least=i;j<data.length;j++) if (data[j]<=data[least]) least=j; if (least!=i) swap(data,least,i); //½»»»data[i]ºÍ×îСԪËØ } return data; } public static void swap(int[]data,int least,int i){ int tmp=data[least]; data[least]=data[i]; data[i]=tmp; } public static void main(String args[]){ int[] t={10,29,12,23,56}; selection_sort(t); for(int i:t){ System.out.print(i+" "); } }}
4.算法效率：
任何情況下，都需要進行n*(n-1)/2次比較，也就是O(n*n)的複雜度
最好情況：數組已經排序，不需要交換任何元素
最壞情況：最大元素在第一個位置而其他元素有序時，需要進行3*(n-1)次交換，即O(n)，也是很好的結果
三。冒泡排序
1。算法偽代碼描述：
bubblesort(data[]) for i=0 to data.length-2 for j=data.length-1 downto i+1 如果順序錯誤，就交換j和j-1位置上的元素
2。實現：
1)ruby語言實現：
def bubble_sort(data) for i in (0..(data.length-2)) j=data.length-1 while j>i if data[j]<data[j-1] data[j],data[j-1]=data[j-1],data[j] #交換 end j-=1 end endenda=[12,3,56,7,89,87]bubble_sort(a)a.each{|i| print i.to_s+" "}
2）java語言實現：
package com.sohu.blog.denns_zane.sort;public class BubbleSort{ public static void bubble_sort(int [] data){ for(int i=0;i<data.length-1;i++) for(int j=data.length-1;j>i;j--) if(data[j]<data[j-1]) swap(data,j,j-1); } public static void swap(int[]data,int least,int i){ int tmp=data[least]; data[least]=data[i]; data[i]=tmp; } public static void main(String args[]){ int[] t={10,29,12,23,56}; bubble_sort(t); for(int i:t){ System.out.print(i+" "); } }}
3。算法效率：
冒泡排序的比較次數近似是插入排序的兩倍，和選擇排序相同；移動次數和插入排序相同，是選擇排序的n倍。可以說，插入排序比冒泡排序快兩倍。
文章轉自莊周夢蝶 ，原文發布時間5.17
最後更新：2017-05-17 11:36:53