1.快速排序
实现：
1.取中间一个数作为支点
2.分别在支点的左右两边进行查找，如果左边查找到比支点大，右边查找到比支点小，就交换位置，如此循环，比支点小的数就排在了左边，比支点大的就排在右边
3.左右两边再用递归排序，就可以完成排序操作
/** *@brief 快速排序 *@params arr 数组 left 起始位置 right总点位置 */ void quickSort(int arr[],int left,int right) { int i = left; int j = right; int pivot = arr[(left + right) / 2]; // 支点 while(i <= j) { while(arr[i] < pivot) { i++; } while(arr[j] > pivot) { j--; } if(i<=j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // 递归 if(left < j) { quickSort(arr,left,j); } if(i < right) { quickSort(arr,i,right); } }
2.冒泡排序
原理：如果当前这个数比下一个数大，则交换位置，经过一次之后最大的数就排到了数组的末尾，以此类推
void bubble(inti arr[],int n) { int i ; int temp; for(i=0;i<n-1;i++) { if(arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } void bubbleSort(int arr[],int n) { int i; for(i = n; i>=1; i--) { bubble(arr,i); } }
3.选择排序
思路：
1.首先在数组中找到最大值并记录其下标
2.然后最大值与数组下标为n-1的交换。
int findMaxPos(int arr[],int n) { int i; int max = arr[0]; int pos = 0; for(int i = 0; i<n; i++) { if(arr[i] > max) { pos = i; max = arr[i]; } } return pos; } void selectSort(int arr[],int n) { while(n > 1) { int pos = findMaxPos(arr,n); int temp = arr[pos]; arr[pos] = arr[n - 1]; arr[n - 1] = temp; n--; } }
4.插入排序
思路：
1.首要条件：两个数及以上
2.取到当前要插入的元素，以前面一个比较，如果小于前面，则需要把前面的大数移位，直到不满足小于的条件，插入相应的位置
void insert(int arr[],int n) { int key = arr[n]; int i = n; while(arr[i - 1] > key) { arr[i] = arr[i - 1]; i--; if(i == 0) { break; } } arr[i] = key; } void insertionSort(int arr[],int n) { int i; for(i=1; i< n; i++) { insert(arr,i); } }
5.二分查找插入排序
/* * 折半查找排序 * 思路： * 1.直接插入排序中，通过二分查找待插入的位置pos * 2.将pos + 1 到 i - 1元素往后移动一个位置 * 3.将带排序的元素复制到pos */ // 二分查找 /* * 如查找的数组是： a[4] =[3,2,1,4] maxLength = 4 key对应数组下标的值; * 第一次查找：pos = 0 * 第二次查找：pos = 1 * 第三次查找：pos = 2 * 第四次查找： */ int findPos(int a[],int maxLength,int key) { int i = 0, low =0, hight = current - 1,pos; while(low <= hight) { pos = (low + hight) / 2; if(a[pos] > key){ // 向左边查找 hight = pos - 1; }else{ low = pos + 1; }else{ return pos; // 返回查找到的位置 } return -1; // 没有找到 } // 插入排序 void binInsertSort(int a[]) { int i = 0, temp,pos,j; for(i = 0; i<a.count; i++) { pos = findPos(a,i,a[i]); temp = a[i]; for(j = i -1;j >= pos;j--) { a[j + 1] = a[j]; // 元素后移 } a[pos] = temp; } }
6.归并排序
思路：就是将两个已经排好序的数组，合成一个排好序的数组
1.先把数组中单个元素看做是已经排好序的堆
2.合并两个相邻的堆，重复多次，就之后剩下两个在进行合并
int *sort(int a[],int b[]) { int maxLength = a.length + b.length int temp[maxLength]; int ai = 0; int bi = 0; int tempi = 0; while(ai < a.length && bi <b.length) { if(a[ai] < b[bi]) { temp[tempi++] = a[ai++]; } else{ temp[tempi++] = b[bi++]; } } // 判断那个数组最长，把长出来的继续添加到temp数组中 while(ai < a.length) temp[tempi++] = a[ai++]; while(bi < b.length) temp[tempi++] = b[bi++]; return temp; }
7.堆排序
思路：
1.先把要排序的数组如a[9]={20,50,20,40,70,10,80,30,60}，构造堆（有大顶堆和小顶堆）
在构造有序堆时，我们开始只需要扫描一半的元素（n/2-1 ~ 0）即可，为什么?
因为(n/2-1)~0的节点才有子节点，如图1，n=8,(n/2-1) = 3 即3 2 1 0这个四个节点才有子节点
2.筛选
3.调整堆 private static void heapSort(int[] arr) {
int len = arr.length -1; for(int i = len/2 - 1; i >=0; i --){ //堆构造 heapAdjust(arr,i,len); }
// 执行到这里，说明根节点(a[0])是最大值或者是最小值了 while (len >=0){ swap(arr,0,len--); //将堆顶元素与尾节点交换后，长度减1，尾元素最大 heapAdjust(arr,0,len); //再次对堆进行调整 } } public static void heapAdjust(int[] arr,int i,int len){ int left,right,j ; while((left = 2*i+1) <= len){ //判断当前父节点有无左节点（即有无孩子节点，left为左节点） right = left + 1; //右节点或者写 2*i+2 j = left; //j"指针指向左节点" if(j < len && arr[left] < arr[right]) //右节点大于左节点 j ++; //当前把"指针"指向右节点 if(arr[i] < arr[j]) //将父节点与孩子节点交换（如果上面if为真，则arr[j]为右节点，如果为假arr[j]则为左节点） swap(arr,i,j); else //说明比孩子节点都大，直接跳出循环语句 break; i = j; } } public static void swap(int[] arr,int i,int len){ int temp = arr[i]; arr[i] = arr[len]; arr[len] = temp; }