公司的网站 优帮云,第三次网站建设的通报,网络推广心得体会,国外著名购物网站排名目录 一.排序相关概念二.常见排序算法1.堆排序2.插入排序3.希尔排序4.选择排序5.冒泡排序6.快速排序1.快速排序--递归(未优化)2.快速排序--递归(优化)3.快速排序--非递归 7.归并排序1.归并排序--递归2.归并排序--非递归 一.排序相关概念
排序#xff1a;使一串记录按照某个关… 目录 一.排序相关概念二.常见排序算法1.堆排序2.插入排序3.希尔排序4.选择排序5.冒泡排序6.快速排序1.快速排序--递归(未优化)2.快速排序--递归(优化)3.快速排序--非递归 7.归并排序1.归并排序--递归2.归并排序--非递归 一.排序相关概念
排序使一串记录按照某个关键字的大小递增或递减的排列起来稳定性在未排序的序列中存在多个具有相同关键字的记录如果在经过排序之后这些记录的相对次序保持不变则称这种排序算法是稳定的内部排序数据元素全部放在内存中的排序外部排序相关元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序
二.常见排序算法
1.堆排序
基本思想建立大/小根堆将堆尾元素(end位置元素)与堆顶元素(堆中最大/小值)交换调整end位置前的所有结点使其重新满足大/小根堆的性质同时end位置向前移动循环这个过程直至end位置移动堆顶位置(每次都将堆的最大/小值移动到堆尾)时间复杂度O(NlogN)空间复杂度O(1)稳定性不稳定 public void heapSort(int[] array) {createBigHeap(array);int end array.length - 1;while (end 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}}public void createBigHeap(int[] array) {for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {siftDown(array, parent, array.length);}}public void siftDown(int[] array, int parent, int end) {int child 2 * parent 1;while (child end) {if (child 1 end array[child] array[child 1]) {child;}if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;} else {break;}}}public void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}2.插入排序
基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列时间复杂度O(N^2^)空间复杂度O(1)稳定性稳定特点元素集合越接近有序插入排序算法的时间效率就越高 public void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];// 获取插入的元素int j i - 1;for (; j 0; j--) { // 寻找要插入的位置if (array[j] tmp) {array[j 1] array[j];} else {break;// 找到了要插入的位置或者没找到(j移动到-1位置)}}array[j 1] tmp;}}3.希尔排序
基本思想先选定一个整数gap把待排序文件中所有记录分成多个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当gap1时所有记录排序完成时间复杂度约O(N^1.25^)~N(1.6*N^1.25^)空间复杂度O(1)稳定性不稳定 public void shellSort(int[] array) {int gap array.length;while (gap 0) {gap gap / 2;shell(array, gap);}}public void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for (; j 0; j--) {if (array[j] tmp) {array[j gap] array[j];} else {break;}}array[j gap] tmp;}}4.选择排序
基本思想每一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置直到全部待排序的数据元素排完时间复杂度O(N^2^)空间复杂度O(1)稳定性不稳定 public void selectSort(int[] array) {for (int i 0; i array.length - 1; i) {int minIndex i;for (int j i 1; j array.length; j) {if (array[j] array[minIndex]) {minIndex j;}}swap(array, i, minIndex);}}public void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}5.冒泡排序
基本思想在待排序的数据元素中将相邻的两个数进行比较若前面的数比后面的数大就交换两数否则不交换循环这个过程直至最终完成排序(小的数据向前移动大的数据向后移动)时间复杂度O(N^2^)空间复杂度O(1)稳定性稳定 public void bubbleSort(int[] array) {for (int i 0; i array.length - 1; i) {boolean flag false;for (int j 0; j array.length - 1 - i; j) {if (array[j] array[j 1]) {swap(array, j, j 1);flag true;}}if (!flag) {return;}}}6.快速排序
基本思想任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上时间复杂度O(NlogN)空间复杂度O(logN)稳定性不稳定
1.快速排序–递归(未优化) public void quickSort(int[] array) {quick(array, 0, array.length - 1);}public void quick(int[] array, int start, int end) {if (start end) {return;}int pivot partition1(array, start, end);// 基准值下标// 左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值quick(array, start, pivot - 1);// 递归左子序列quick(array, pivot 1, end);// 递归右子序列}// 将区间按照基准值划分为左右两半部分的常见方式:Hoare法和挖坑法// Hoare法public int partition1(int[] array, int left, int right) {// left和right分别为array子序列的最左和最右元素下标int tmp array[left];// 基准值int start left;while (left right) {// right向前走,寻找基准值的元素下标while (left right array[right] tmp) {right--;}// left向后走,寻找基准值的元素下标while (left right array[left] tmp) {left;}// 交换left和right下标的元素swap(array, left, right);}// left和right相遇,将基准值与相遇位置元素交换swap(array, start, left);return left;}// 挖坑法public int partition2(int[] array, int left, int right) {int tmp array[left];// left下标元素填入tmp中,留下一个坑(left下标)while (left right) {// right向前走,寻找基准值的元素下标while (left right array[right] tmp) {right--;}array[left] array[right];// 填入坑(left下标)中,留下一个坑(right下标)// left向后走,寻找基准值的元素下标while (left right array[left] tmp) {left;}array[right] array[left];// 填入坑(right下标)中,留下一个坑(left下标)}// left和right相遇,将tmp填入相遇位置这个坑中array[left] tmp;return left;}2.快速排序–递归(优化)
三数取中法选key(减少划分区间时没有左/右子序列的情况)递归到小的区间时使用插入排序 public void quickSort(int[] array) {quick(array, 0, array.length - 1);}public void quick(int[] array, int start, int end) {if (start end) {return;}if (start - end 1 10) { // 子序列长度较短时,使用插入排序insertSortSTE(array, start, end);return;}int mid middle(array, start, end);// 获取中间值的下标swap(array, start, mid);// 交换start和mid下标元素,使得基准值为mid元素int pivot partition1(array, start, end);quick(array, start, pivot - 1);quick(array, pivot 1, end);}public int middle(int[] array, int left, int right) { // 三数取中法(left,mid,right)int mid left ((right - left) 1);int[] num {array[left], array[mid], array[right]};Arrays.sort(num);if (array[left] num[1]) {return left;} else if (array[right] num[1]) {return right;} else {return mid;}}// 指定区间插入排序public void insertSortSTE(int[] array, int start, int end) {for (int i start 1; i end; i) {int tmp array[i];int j i - 1;for (; j start; j--) {if (array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}3.快速排序–非递归 public void quickSortNor(int[] array) {int left 0;int right array.length - 1;int pivot partition1(array, left, right);StackInteger stack new Stack();if (pivot - 1 left) {stack.push(left);stack.push(pivot - 1);}if (pivot 1 right) {stack.push(pivot 1);stack.push(right);}while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition1(array, left, right);if (pivot - 1 left) {stack.push(left);stack.push(pivot - 1);}if (pivot 1 right) {stack.push(pivot 1);stack.push(right);}}}7.归并排序
基本思想归并排序是建立在归并操作上的一种有效的排序算法,为分治法的一个典型应用即将待排序的数据分段排序后合并时间复杂度O(NlogN)空间复杂度O(N)稳定性稳定
1.归并排序–递归 public void mergeSort(int[] array) {branch(array, 0, array.length - 1);}public void branch(int[] array, int left, int right) {if (left right) {return;}int mid left ((right - left) 1);branch(array, left, mid);// 分解左子序列branch(array, mid 1, right);// 分解右子序列merge(array, left, mid, right); // 合并子序列}public void merge(int[] array, int left, int mid, int right) {int s1 left;int e1 mid;int s2 mid 1;int e2 right;int index 0;int[] ans new int[right - left 1];while (s1 e1 s2 e2) {if (array[s1] array[s2]) {ans[index] array[s1];} else {ans[index] array[s2];}}while (s1 e1) {ans[index] array[s1];}while (s2 e2) {ans[index] array[s2];}for (int i left; i right; i) {array[i] ans[i - left];}}2.归并排序–非递归 public void merge(int[] array, int left, int mid, int right) {int s1 left;int e1 mid;int s2 mid 1;int e2 right;int index 0;int[] ans new int[right - left 1];while (s1 e1 s2 e2) {if (array[s1] array[s2]) {ans[index] array[s1];} else {ans[index] array[s2];}}while (s1 e1) {ans[index] array[s1];}while (s2 e2) {ans[index] array[s2];}for (int i left; i right; i) {array[i] ans[i - left];}}public void mergeSortNor(int[] array) {int gap 1;while (gap array.length) {for (int i 0; i array.length; i) {int left i;int mid left gap - 1;if (mid array.length) {mid array.length - 1;}int right mid gap;if (right array.length) {right array.length - 1;}merge(array, left, mid, right);}gap * 2;}}
