数据结构7

文章目录

排序和查找的关系选择排序（不稳定）冒泡排序（不快）插入排序（推荐）程序验证器快速排序快速排序（C语言实现）

排序和查找的关系

排序是查找的前提排序是重点。排序： 冒泡插入选择快速排序归并排序

选择排序（不稳定）

理解选择排序的不稳定性

// 选择排序 public int[] selectedSort(int[] intArr) { if (intArr == null || intArr.length == 0) { throw new RuntimeException("数据不合法"); } for (int i = 0; i < intArr.length - 1; i++) { int index = i; for (int j = i; j < intArr.length - 1; j++) { index = (intArr[index] > intArr[j + 1]) ? (j + 1) : index; } int k = intArr[i]; intArr[i] = intArr[index]; intArr[index] = k; } return intArr; }

冒泡排序（不快）

// 冒泡排序 public int[] maopaoSort(int[] intArr) { if (intArr == null || intArr.length == 0) { throw new RuntimeException("数据不合法"); } for (int i = intArr.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (intArr[j] > intArr[j + 1]) { int k = intArr[j]; intArr[j] = intArr[j + 1]; intArr[j + 1] = k; } } } return intArr; }

插入排序（推荐）

// 插入排序 public int[] charuSort(int[] intArr) { if (intArr == null || intArr.length == 0) { throw new RuntimeException("数据不合法"); } for (int i = 1; i < intArr.length; i++) { for (int j = i; j > 0; j--) { if (intArr[j] < intArr[j - 1]) { int k = intArr[j]; intArr[j] = intArr[j - 1]; intArr[j - 1] = k; } } } return intArr; }

程序验证器

// 正确性检测 @Test public void sortTest() { int[] arr = new int[50]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) Math.round(Math.random() * 100); } System.out.println(Arrays.toString(arr)); int[] copyOf = Arrays.copyOf(arr, arr.length); Arrays.sort(copyOf); System.out.println(Arrays.toString(copyOf)); // 此处引入自定义的排序方法 int[] selected = charuSort(arr); System.out.println(Arrays.toString(selected)); boolean flag = true; for (int i = 0; i < arr.length; i++) { if (copyOf[i] != selected[i]) { flag = false; break; } } System.out.println(flag); }

快速排序

快速排序（C语言实现）

// 快速排序 #include<stdio.h> int FindPos(int * a,int low,int high)； void QuickSort(int * a,int low,int high)； int main(void){ int a[6] = {2,1,0,5,4,3}; int i; QuickSort(a,0,5);// 第二个参数表示第一个元素的下标，第三个参数表示最后一个元素的下标 for(i = 0;i<6;++i) printf("%d",a[i]); printf("\n"); return 0; } void QuickSort(int * a,int low,int high){ int pos; if(low < high){ pos = FindPos(a,low,high); QuickSort(a,low,pos-1); QuickSort(a,pos+1,high); } } int FindPos(int * a,int low,int high){ int val = a[low]; while(low < high){ while(low < high && a[high] >= val) --high; a[low] = a[high]; while(low < high && a[low] <= val) ++low; a[high] = a[low]; }// 终止while循环之后，low和high一定是相等的 a[low] = val; return low; // high }