排序算法合集

　　由于时间原因,我在复习的时候只写了核心部分.大家有需要可以自己补充完整调试.
　　public class SelectSort //选择排序 { 	     public static int[] selectSort(int[] a)  		 { 		         int n = a.length; 		      for (int i = 0; i < n - 1; i++)  			  { 			             int min = i; 			            for (int j = i + 1; j < n; j++)  						{ 				              if (a[min] > a[j]) min = j; 			 			    } 		           //交换 				        int temp = a[i]; 			            a[i] = a[min]; 			            a[min] = temp; 			 		   } 		       return a; 	 	     }  }//插入排序   public class InsertSort {      public static int[] insertSort(int[] arr) {           if(arr == null || arr.length < 2)          return arr;            int n = arr.length;        for (int i = 1; i < n; i++) {             int temp = arr[i];              int k = i - 1;             while(k >= 0 && arr[k] > temp)                 k--;             //腾出位置插进去,要插的位置是 k + 1;            for(int j = i ; j > k + 1; j--)                arr[j] = arr[j-1];             //插进去             arr[k+1] = temp;          }          return arr;      } }//冒泡排序法 public class BubbleSort  {       public static int[] bubbleSort(int[] arr)        {           if (arr == null || arr.length < 2)           {              return arr;           }           int n = arr.length;           for (int i = 0; i < n; i++)           {               boolean flag = true;            for (int j = 0; j < n -i - 1; j++)            {                 if (arr[j + 1] < arr[j])                 {                    flag = false;                    int t = arr[j];                     arr[j] = arr[j+1];                     arr[j+1] = t;                             }             }             //一趟下来是否发生位置交换              if(flag)                 break;         }          return arr;     } }void BubbleSort(int array[], int len)//冒泡的其他实现方法 { 	int i = 0; 	int j = 0; 	int exchange = 1; 	for (i = 0; (i < len) && exchange; i++) 	{ 		exchange = 0; 		for (j = len; j > 1; j--) 		{ 			if (array[j] < array[j - 1]) 			{ 				swap(array, j, j - 1); 					exchange = 1; 			} 		} 	} }//希尔排序 public class ShellSort {     public static int[] shellSort(int arr[]) {         if (arr == null || arr.length < 2) return arr;         int n = arr.length;         // 对每组间隔为 h的分组进行排序，刚开始 h = n / 2;         for (int h = n / 2; h > 0; h /= 2) {              //对各个局部分组进行插入排序               for (int i = h; i < n; i++) {                  // 将arr[i] 插入到所在分组的正确位置上                insertI(arr, h, i);               }      }       return arr;    }      /**       * 将arr[i]插入到所在分组的正确位置上       * arr[i]] 所在的分组为 ... arr[i-2*h],arr[i-h], arr[i+h] ...      */     private static void insertI(int[] arr, int h, int i) {         int temp = arr[i];       int k;         for (k = i - h; k > 0 && temp < arr[k]; k -= h) {            arr[k + h] = arr[k];         }          arr[k + h] = temp;     }  }//归并排序 //A数组和B数组归并为C数组 void Merge(int src[], int des[], int low, int mid, int high)//src[]数组首地址,des[]拷贝目的地,A数组的前面,中间, {//B数组的前面  high后面 	int i = low; 	int j = mid + 1;//赋值过程,就是相当于让前面的去操作了 	int k = low; 	while ((i < mid) && (j <= high)//把小的放在目的地中 	{ 		if (src[i] < src[j]) 		{ 			des[k++] = src[i++];  		} 		else 		{ 			des[k++] = src[j++]; 		} 	} 	while (i <= mid)//如果A还剩下几个尾部元素 	{ 		des[k++] = src[i++]; 	} 	while (j <= mid)//如果B还剩下几个尾部元素 	{ 		des[k++] = src[j++]; 	}  } //调用子序列 //每次分为2路,当只剩下一个元素时,就不需要在划分, void MSort(int src[], int des[], int low, int max, int high) { 	if (low == high)//只有一个元素,不需要归并 	{ 		des[low] = src[low];  	} 	else//多个元素开始进行划分 	{ 		int mid = (low + high) / 2; 		int*space = (int*)malloc(sizeof(int)*max); 		//递归进行2路划分,递归划分结束,开始归并操作 		if (space != NULL) 		{ 			Msort(src, space, low, mid, max); 			Msort(src, space,  mid+1,high, max); 			Merge(src, space, low, mid, high);//调用归并函数进行归并  		} 		free(space); 	} } void MergeSort(int array[], int len) { 	Msort(array, array, 0, len - 1, len); }//堆排序 //是树形选择排序方法,类似于完全二叉树的顺序存储结构,利用孩子节点和双亲节点的关系索引 var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr) {   // 建立大顶堆     len = arr.length;     for (var i = Math.floor(len/2); i >= 0; i--) {         heapify(arr, i);     } }   function heapify(arr, i) {     // 堆调整     var left = 2 * i + 1,         right = 2 * i + 2,         largest = i;       if (left < len && arr[left] > arr[largest]) {         largest = left;     }       if (right < len && arr[right] > arr[largest]) {         largest = right;     }       if (largest != i) {         swap(arr, i, largest);         heapify(arr, largest);     } }   function swap(arr, i, j) {     var temp = arr[i];     arr[i] = arr[j];     arr[j] = temp; }   function heapSort(arr) {     buildMaxHeap(arr);       for (var i = arr.length - 1; i > 0; i--) {         swap(arr, 0, i);         len--;         heapify(arr, 0);     }     return arr; }//基数排序 var counter = []; function radixSort(arr, maxDigit) {     var mod = 10;     var dev = 1;     for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {         for(var j = 0; j < arr.length; j++) {             var bucket = parseInt((arr[j] % mod) / dev);             if(counter[bucket]==null) {                 counter[bucket] = [];             }             counter[bucket].push(arr[j]);         }         var pos = 0;         for(var j = 0; j < counter.length; j++) {             var value = null;             if(counter[j]!=null) {                 while ((value = counter[j].shift()) != null) {                       arr[pos++] = value;                 }           }         }     }     return arr; }
　　排序算法远远不止上面这些,目前我也用不到更复杂的算法,所以就没去研究.只过一下这些常规的算法