和朋友做了个小决定，把以前学过的小算法一个一个复习一遍。
1、快排
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public class Quick_sort { /** * @author bbking * @date 2014/4/9*/ public static void quickSort(int[] arr,int left,int right){ if(left < right) { int i = left, j = right , x = arr[left]; //取数组第一个元素为中值 while( i < j) { while(i < j && arr[j] >= x) //从右往左找到第一个小于x的值 j--; if(i < j) arr[i++] = arr[j]; //与当前i位置元素交换,i++ while(i < j && arr[i] < x) //从左往找到第一个大于x的值 i++; if(i < j) arr[j--] = arr[i]; //与当前j位置元素交换,j-- } arr[i] = x; //赋中值 quickSort(arr,left,i-1); //对前半部进行递归排序 quickSort(arr,i+1,right); //对后半部进行递归排序 } } //测试例子 public static void main(String[] args) { int arr[] = {7,5,8,4,9,2,1,4,6,10,-3,0}; quickSort(arr,0,arr.length-1); for(int i = 0; i < 12; i ++) System.out.println(arr[i]); } }
递归的实现很容易理解，但数据规模很大时，递归的算法很容易导致栈溢出，所以我们需要改为非递归，这里我们需要模拟系统栈对left和right的存储情况。
#include <iostream> #include <cstdio> #include <stack> #include <algorithm> using namespace std; void quick_sort(int *arr ,int left ,int right) { //Stack存放原则：待分治的数组的开始和结束坐标，第一个为开始坐标，第二个为结束坐标 stack<int> Stack; Stack.push(left); Stack.push(right); while (Stack.empty() != true) { int tempJ ,j, tempI ,i; tempJ = j = Stack.top(); Stack.pop(); tempI = i = Stack.top(); Stack.pop(); int key = arr[i]; while(i<j) { while (i < j && arr[j] >= key) j --; if(i < j) swap(arr[i],arr[j]); while (i < j && arr[i] < key) i ++; if(i < j) swap(arr[i],arr[j]); } if(i > tempI) { Stack.push(tempI); Stack.push(i-1); } if (i < tempJ) { Stack.push(i+1); Stack.push(tempJ); } } } int main()
{ int arr[] = {5,6,3,2,7,8,1,9,15,12,13}; int size = sizeof(arr)/sizeof(arr[0]); quick_sort(arr ,0,size-1); for(int i = 0 ; i < size; i ++ ) { cout << arr[i]<<" "; } cout << endl; system("pause"); return 0; }
原文：http://www.cnblogs.com/chenbjin/p/3655376.html
