[冒泡排序算法]、[选择排序算法]
1 /** 2 * @Description:冒泡排序算法实现
3 * @time:2016/03/29 下午14:40 4 */ 5 public static void bubbleSort(int[] arr) { 6 7 if (arr == null || arr.Length == 0) 8 return; 9 for (int i = 0; i < arr.Length - 1; i++) {10 for (int j = arr.Length - 1; j >i; j--)11 {12 if (arr[j] < arr[j - 1]) {13 swap(arr, j - 1, j);14 }15 }16 }17 }18 19 public static void swap(int[] arr, int i, int j) {20 int temp = arr[i];21 arr[i] = arr[j];22 arr[j] = temp;23 }
1 /* 2 * @Description:选择排序算法实现
3 * @time:2016/03/29 下午14:42 4 */ 5 6 public static void selectSort(int[] arr) { 7 if (arr == null || arr.Length == 0) 8 return; 9 int minIndex = 0;10 for (int i = 0; i < arr.Length - 1; i++) { //只需要比较n-1次 11 minIndex = i;12 for (int j = i + 1; j < arr.Length; j++) { //从i+1开始比较，因为minIndex默认为i了,i就没必要比了。13 if (arr[j] < arr[minIndex]) {14 minIndex = j;15 }16 }17 if (minIndex != i) { //如果minIndex不为i,说明找到了更小的值，交换之。18 swap(arr, i, minIndex);19 20 }21 }22 23 }24 25 public static void swap(int[] arr, int i, int j) {26 int temp = arr[i];27 arr[i] = arr[j];28 arr[j] = temp;29 }
插入排序算法
1 public static void insertSort(int[] arr) { 2 if (arr == null || arr.Length == 0) 3 return; 4 for (int i = 1; i < arr.Length; i++) { //假设第一个数位置正确的；要往后移，必须要假设第一个 5 int j = i; 6 int target = arr[i]; //待插入的 7 8 //后移 9 while (j > 0 && target < arr[j - 1]) {10 arr[j] = arr[j - 1];11 j--;12 }13 //插入14 arr[j] = target;15 }16 } 快速排序算法
1 //一次划分 2 public static int partition(int[] arr, int left, int right) 3 { 4 int pivotKey = arr[left]; 5 int pivotPointer = left; 6 7 while (left < right) 8 { 9 while (left < right && arr[right] >= pivotKey)10 right--;11 while (left < right && arr[left] <= pivotKey)12 left++;13 swap(arr, left, right); //把大的交换到右边，把小的交换到左边。14 }15 swap(arr, pivotPointer, left); //最后把pivot交换到中间16 return left;17 18 }19 20 public static void quickSort(int[] arr, int left, int right)21 {22 if (left >= right)23 return;24 int pivotPos = partition(arr, left, right);25 quickSort(arr, left, pivotPos - 1);26 quickSort(arr, pivotPos + 1, right);27 }28 29 public static void sort(int[] arr)30 {31 if (arr == null || arr.Length == 0)32 return;33 quickSort(arr, 0, arr.Length - 1);34 }35 36 public static void swap(int[] arr, int left, int right)37 {38 int temp = arr[left];39 arr[left] = arr[right];40 arr[right] = temp;41 }42 43 ====================================优化以上代码44 public static int partition(int[] arr, int left, int right)45 {46 int pivotKey = arr[left];47 while (left < right)48 {49 while (left < right && arr[right] >= pivotKey)50 right--;51 arr[left] = arr[right]; //把小的移动到左边52 while (left < right && arr[left] <= pivotKey)53 left++;54 arr[right] = arr[left];//把大的移动到右边55 }56 arr[left] = pivotKey; //最后把pivot赋值到中间57 return left;58 59 }60 61 public static void quickSort(int[] arr, int left, int right)62 {63 if (left >= right)64 return;65 int pivotPos = partition(arr, left, right);66 quickSort(arr, left, pivotPos - 1);67 quickSort(arr, pivotPos + 1, right);68 }69 public static void sort(int[] arr)70 {71 if (arr == null || arr.Length == 0)72 return;73 quickSort(arr, 0, arr.Length - 1);74 } 希尔排序
1 static void Main(string[] args) 2 { 3 int[] arr={ 1,22,32,13,35,42,48,55}; 4 shellSort(arr); 5 for (int i = 0; i < arr.Length; i++) 6 { 7 Console.Write("{0},", arr[i]); 8 } 9 Console.ReadLine();10 }11 12 public static void shellInsert(int[] arr, int d) {13 for (int i = d; i < arr.Length; i++) {14 int j = i - d;15 int temp = arr[i]; //记录要插入的数据16 while (j >= 0 && arr[j] > temp) { //从后向前，找到比其小的数的位置 17 arr[j + d] = arr[j]; //向后挪动18 j -= d;19 }20 21 if (j != i - d) //存在比其小的数22 arr[j + d] = temp;23 24 }25 }26 public static void shellSort(int[] arr) {27 if (arr == null || arr.Length == 0)28 return;29 int d = arr.Length / 2;30 while (d >= 1) {31 shellInsert(arr, d);32 d /= 2;33 }34 } 归并排序
1 static void Main(string[] args) 2 { 3 int[] arr={ 1,22,32,13,35,42,48,55}; 4 mergeSort(arr); 5 for (int i = 0; i < arr.Length; i++) 6 { 7 Console.Write("{0},", arr[i]); 8 } 9 Console.ReadLine();10 }11 12 public static void mergeSort(int[] arr) {13 mSort(arr, 0, arr.Length - 1);14 }15 16 public static void mSort(int[] arr, int left, int right) {17 if (left >= right)18 return;19 int mid = (left + right) / 2;20 21 mSort(arr, left, mid);22 mSort(arr, mid + 1, right);23 merge(arr, left, mid, right);24 }25 26 public static void merge(int[] arr, int left, int mid, int right) { 27 //[left,mid][mid+1,right]28 int[] temp = new int[right - left + 1];29 30 int i = left;31 int j = mid + 1;32 int k = 0;33 while (i <= mid && j <= right) {34 if (arr[i] <= arr[j])35 {36 temp[k++] = arr[i++];37 }38 else {39 temp[k++] = arr[j++];40 }41 }42 43 while (i <= mid) {44 temp[k++] = arr[i++];45 }46 47 while (j <= right) {48 temp[k++] = arr[j++];49 }50 51 for (int p = 0; p < temp.Length; p++) {52 arr[left + p] = temp[p];53 }54 55 }