对数组排序的三种通用方法：
交换排序Exchange
选择排序Selection
插入排序Insertion
我们通过一叠扑克牌形象地理解以上三种方法。
用交换方法对扑克牌排序时，把扑克牌摊在桌上，花色朝上然后交换顺序已乱的牌，直到一副牌都有序为止。
用选择方法对扑克牌排序时，把牌摊在桌上，把数值最小的牌抽出，放在手中。然后在剩余牌中再找到最小者，把其放在手中，如此继续到桌上无牌时，手中的牌就排好序了。
用插入方法对扑克牌排序时，把牌都拿在手中，每次从手中取一张放在桌上，每次放到桌上时，都插入适当位置，如此继续，手中无牌时，桌上的一副牌就变成有序的了。
交换排序中，最著名（也是最声名狼藉）的排序似乎冒泡排序，出名在于名字形象且操作简单，其名声狼藉在于它是目前最差的排序之一。两个for循环重复了指定的次数，外部循环执行n-1次，内部循环执行你n/2次。
选择排序中，先选择最小的元素并将其与第一元素交换，然后在剩余n-1个元素中选择最小者并与第二个元素交换等等，
不幸的是和冒泡算法一样，，外部循环执行n-1次，内部循环执行你n/2次
插入排序，与冒泡和选择排序不同，插入排序的比较次数与被排表的初始排列有关。如表是完全有序的，比较次数为n-1，否则按n平方次序列排序。
快速排序基于交换排序，与基于交换排序的冒泡排序相比，其效果是令人吃惊的。
快速排序的基本思想是分区。一般过程是先选一个称为比较数的值，然后把数组分成两段。大于或等于分区值的元素都放在一边，小于分区值的元素都放另一边。然后对两段用递归排序。
快速排序算法如下：
- using System;
- using System.Collections.Generic;
- using System.Text;
- namespace ConsoleApplication1
- {
- class DataStructDemo
- {
- public static void QuickSort(int [] items, int left, int right){
- int i,j,x,y;
- i=left;
- j=right;
- x=items[(left+right)/2];
- do
- {
- while ((items[i] < x) && (i < right))
- i++;
- while ((items[j] > x) && (j > left))
- j--;
- if (i <= j)
- {
- y = items[i];
- items[i] = items[j];
- items[j] = y;
- i++;
- j--;
- }
- } while (i <= j);
- if(left<j)QuickSort(items,left,j);
- if(right>i)QuickSort(items,i,right);
- }
- [STAThread]
- static void Main(string[] args)
- {
- int[] arr ={ 2, 4, 65, 76, 87, 90, 56, 89, 78 };
- QuickSort(arr, 0, arr.Length - 1);
- Console.WriteLine(" Quick Sort Test!!!");
- for (int i = 0; i < arr.Length; i++)
- {
- Console.WriteLine(arr[i]);
- }
- }
- }
- }
该例中，x=items[(left+right)/2]值为87，当第一次
- do
- {
- while ((items[i] < x) && (i < right))
- i++;
- while ((items[j] > x) && (j > left))
- j--;
- if (i <= j)
- {
- y = items[i];
- items[i] = items[j];
- items[j] = y;
- i++;
- j--;
- }
- } while (i <= j);
这段代码执行完毕后，i值为6，j值为5，执行的结果为
2, 4 65 76 78 56 90 89 87。
中间过程为
2, 4 65 76 87 90 56 89 78
2 4 65 76 78 90 56 89 87
2 4 65 76 78 90 56 89 87
2, 4 65 76 78 56 90 89 87
这时j左边及i右边被分成了两段，左段都比x=items[(left+right)/2]=87小。右段都比x=items[(left+right)/2]=87大，同时if(left<j)QuickSort(items,left,j)条件满足，if(right>i)QuickSort(items,i,right)条件也满足，将递归对两段排序。
算法最后的执行结果为
