演算法大全

前言

演算法是在有bai限步驟內求解某一問題所使用的一組定義明確的規則，通俗點說，就是計算機解題的程序，在這個程序中，無論是形成解題思路還是撰寫程式，都是在實施某種演算法，解題思路可以用偽語言，撰寫程式用某種特定語言，

一、希爾排序

1.演算法思想簡單描述：

• 在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，并且對插入下一個數沒有提供任何幫助，
• 如果比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換，
• D.L.shell于1959年在以他名字命名的排序演算法中實作了這一思想，
• 演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量
  對它進行，在每組中再進行排序，
• 當增量減到1時，整個要排序的數被分成一組，排序完成，

2.希爾排序演算法實作：

要求：
初次取序列的一半為增量，以后每次減半，直到增量為1，

public class ShellSorter
{
    public void Sort(int[] list)
    {
        int inc;
        for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
        for (; inc > 0; inc /= 3)
        {
            for (int i = inc + 1; i <= list.Length; i += inc)
            {
                int t = list[i - 1];
                int j = i;
                while ((j > inc) && (list[j - inc - 1] > t))
                {
                    list[j - 1] = list[j - inc - 1];
                    j -= inc;
                }
                list[j - 1] = t;
            }
        }
    }
}

 

public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
ShellSorter sh=new ShellSorter();
sh.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);
}
}

二、插入排序

1.演算法思想簡單描述：

• 在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的，
• 如此反復回圈，直到全部排好順序，
• 直接插入排序是穩定的，演算法時間復雜度O(n2)–[n的平方]

2.插入排序演算法實作：

代碼如下（示例）：

public class InsertionSorter
{
    public void Sort(int[] list)
    {
        for (int i = 1; i < list.Length; ++i)
        {
            int t = list[i];
            int j = i;
            while ((j > 0) && (list[j - 1] > t))
            {
                list[j] = list[j - 1];
                --j;
            }
            list[j] = t;
        }

    }
}

 

public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
InsertionSorter ii=new InsertionSorter();
ii.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);
}
}

三、選擇排序

1.演算法思想簡單描述：

在要排序的一組數中，選出最小的一個數與第一個位置的數交換；
然后在剩下的數當中再找最小的與第二個位置的數交換，如此回圈
到倒數第二個數和最后一個數比較為止，

選擇排序是不穩定的，演算法復雜度O(n2)–[n的平方]

2.選擇排序演算法實作：

代碼如下（示例）：

public class SelectionSorter
{
    private int min;

    public void Sort(int[] list)
    {
        for (int i = 0; i < list.Length - 1; ++i)
        {
            min = i;
            for (int j = i + 1; j < list.Length; ++j)
            {
                if (list[j] < list[min])
                    min = j;
            }
            int t = list[min];
            list[min] = list[i];
            list[i] = t;
        }

    }
}

 

public class MainClass
{
public static void Main()
{
int[] iArrary=new int[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47};
SelectionSorter ss=new SelectionSorter();
ss.Sort(iArrary);
for(int m=0;m<=13;m++)
Console.WriteLine("{0}",iArrary[m]);

}
}

四、冒泡排序：

1.演算法思想簡單描述：

• 依次比較相鄰的兩個數,把大的放前面,小的放后面.即首先比較第1個數和第2個數,大數放前,小數放后.然后比較第2個數和第3個數…直到比較最后兩個數.第一趟結束,最小的一定沉到最后.重復上程序,仍從第1個數開始,到最后第2個數.然后…
• 由于在排序程序中總是大數往前,小數往后,相當氣泡上升,所以叫冒泡排序

演算法原理：

• 比較相鄰的元素，如果第一個比第二個大，就交換他們兩個，

• 對每一對相鄰元素做同樣的作業，從開始第一對到結尾的最后一對，在這一點，最后的元素應該會是最大的數，

• 針對所有的元素重復以上的步驟，除了最后一個，

• 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較，

2.冒泡排序演算法實作：

代碼如下（示例）：

public void BubbleSort(int[] arr){
		for(int i=0;i<arr.length-1;i++){ 
			for(int j=0;j<arr.length-1-i;j++){
				if(arr[j]>arr[j+1]){ //相鄰兩個元素作比較，如果前面元素大于后面，進行交換
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

五、總結

這個是最近發覺有人詢問博主，能不能做一期演算法的詮釋，肖塵想了一下，覺得還是滿足大家，演算法也算是程式員需要掌握的，博主一開始學演算法時，也是挺混亂，不懂怎么去學，幸得學長幫助！
所以，大家一起努力加油!