10. 排序

一、排序的概念及引用

1. 排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

内部排序:数据元素全部放在内存中的排序。

外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 

2. 常见的排序算法

二、常见排序算法的实现

1. 插入排序

基本思想:直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。

1.1 直接插入排序

假设在排序过程中,待排序表 L[1...n] 在某次排序过程中的某一时刻状态如下:

要将元素 L(i) 插入已有序的子序列 L[1...i-1],需要执行以下操作(为避免混淆,下面用L[ ]表示一个表,而用 L() 表示一个元素):

  1. 査找出 L(i) 在 L[1...i-1] 中的插入位置 k。
  2. 将 L[k...i-1] 中的所有元素依次后移一个位置。
  3. 将 L(i)复制到 L(k)。

为了实现对 L[1...n] 的排序,可以将 L(2)~L(n) 依次插入前面已排好序的子序列,初始L[1]可以视为一个已排好序的子序列。上述操作执行 n-1次就能得到一个有序的表。

//直接插入排序
public static void insertSort(int[] array){for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i-1;for (; j >= 0; j--) {if(array[j] <= temp){break;}array[j+1] = array[j];}array[j+1] = temp;}
}

【直接插入排序算法的性能分析】

  • 空间效率:仅使用了常数个辅助单元,因而空间复杂度为 O(1)
  • 时间效率:在排序过程中,向有序子表中逐个地插入元素的操作进行了 n-1 趟,每趟操作都分为比较关键字和移动元素,而比较次数和移动次数取决于待排序表的初始状态。在最好情况下,表中元素已经有序,此时每插入一个元素,都只需比较一次而不用移动元素,因而时间复杂度为O(n)。在最坏情况下,表中元素顺序刚好与排序结果中的元素顺序相反(逆序),总的比较次数达到最大,总的移动次数也达到最大,总的时间复杂度为O(n^{2})平均情况下,考虑待排序表中元素是随机的,此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度,总的比较次数与总的移动次数均约为n^{2}/4
    因此,直接插入排序算法的时间复杂度为 O(n^{2})
  • 稳定性:因为每次插入元素时总是从后往前先比较再移动,所以不会出现相同元素相对位置发生变化的情况,即直接插入排序是一个稳定的排序算法。
  • 适用性:直接插入排序适用于顺序存储链式存储的线性表,采用链式存储时无须移动元素。

1.2 折半插入排序

从直接插入排序算法中,不难看出每趟插入的过程中都进行了两项工作:①从前面的有序子表中查找出待插入元素应该被插入的位置;②给插入位置腾出空间,将待插入元素复制到表中的插入位置。注意到在该算法中,总是边比较边移动元素。下面将比较和移动操作分离,即先折半查找出元素的待插入位置,然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时,可以对直接插入排序算法做如下改进:因为是顺序存储的线性表,所以查找有序子表时可以用折半查找来实现。确定待插入位置后,就可统一地向后移动元素。

//折半插入排序
public static void insertSort2(int[] array){for (int i = 1; i < array.length; i++) {int temp = array[i];int low = 0;int high = i-1;//这里当low == high时,还需要high再往前走一步,才能确保每次都插入到high后面一位。while (low <= high){int mid = (low+high)/2;if(array[mid] > temp){high = mid-1;}else{low = mid+1;}}for (int j = i-1; j > high ; j--) {array[j+1] = array[j];}array[high+1] = temp;}
}

【折半插入排序算法的性能分析】

  • 空间效率:仅使用了常数个辅助单元,因而空间复杂度为 O(1)
  • 时间效率:从上述算法中,不难看出折半插入排序仅减少了比较元素的次数,时间复杂度约为 O(n\log_{2}n),该比较次数与待排序表的初始状态无关,仅取决于表中的元素个数n;而元素的移动次数并未改变它依赖于待排序表的初始状态。因此,折半插入排序的时间复杂度仍为 O(n^{2}),但对于数据量不很大的排序表,折半插入排序往往能表现出很好的性能。
  • 稳定性:折半插入排序是一种稳定的排序算法。
  • 适用性:折半插入排序仅适用于顺序存储的线性表。

1.3 希尔排序(缩小增量排序)

从前面的分析可知,直接插入排序算法的时间复杂度为O(n^{2}),但若待排序列为“正序”时,其时间效率可提高至 O(n),由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的,又称缩小增量排序。希尔排序的过程如下:

  1. 先取一个小于n的增量gap,把表中的全部记录分成gap组,所有距离为gap的倍数的记录放在同一组,在各组内进行直接插入排序;
  2. 然后取第二个增量gap(必须要小于前一个),重复上述过程,直到所取到的gap=1,即所有记录已放在同一组中,再进行直接插入排序;
  3. 由于此时已经具有较好的局部有序性,因此可以很快得到最终结果。

//希尔排序
public static void shellSort(int[] array){int gap = array.length/2;for (; gap >= 1; gap = gap/2) {for (int i = gap; i < array.length; i++) {int temp = array[i];int j = i-gap;for (; j >= 0; j = j-gap){if(array[j] > temp){array[j+gap] = array[j];}else {break;}}array[j+gap] = temp;}}
}

【希尔排序算法的性能分析】

  • 空间效率:仅使用了常数个辅助单元,因而空间复杂度为(1)。
  • 时间效率:因为希尔排序的时间复杂度依赖于增量序列的函数,这涉及数学上尚未解决的难题,所以其时间复杂度分析比较困难。当n在某个特定范围时,希尔排序的时间复杂度约为 O(n^{1.3})。在最坏情况下希尔排序的时间复杂度为 O(n^{2})
  • 稳定性:当相同关键字的记录被划分到不同的子表时,可能会改变它们之间的相对次序,因此希尔排序是一种不稳定的排序算法。例如,上图中两个5的相对次序已发生了变化。
  • 适用性:希尔排序仅适用于顺序存储的线性表。

2. 选择排序

基本思想:每一趟 (如第 i 趟) 在后面 n-i+1 (i = 1,2,…,n-1)个待排序元素中选取关键字最小的元素,作为有序子序列的第 i 个元素,直到第n-1趟做完,待排序元素只剩下1个,就不用再选。

2.1 直接选择排序

假设排序表为L[1...n],第 i 趟排序即从 L[i...n] 中选择关键字最小的元素与L(i)交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可使得整个排序表有序。其排序过程如下:

【直接选择排序算法的性能分析】

  • 空间效率:仅使用常数个辅助单元,所以空间效率为O(1)。
  • 时间效率:从上述伪码中不难看出,在简单选择排序过程中,元素移动的操作次数很少,不会超过 3(n-1) 次,最好的情况是移动0次,此时对应的表已经有序;但元素间比较的次数与序列的初始状态无关,始终是 n(n-1)/2 次,因此时间复杂度始终是 O(n^{2})
  • 稳定性:在第 i 趟找到最小元素后,和第 i 个元素交换,可能会导致第 i 个元素与含有相同关键字的元素的相对位置发生改变。例如,表L = {2, 2, 1},排序结束后,最终排序序列是L = {1, 2, 2},显然,2与2的相对次序已发生变化。因此,简单选择排序是一种不稳定的排序算法。
  • 适用性:简单选择排序适用于顺序存储链式存储的线性表,以及关键字较少的情况。
//直接选择排序
public static void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int min = i;for (int j = i+1; j < array.length; j++) {if(array[j] < array[min]){min = j;}}int temp = array[i];array[i] = array[min];array[min] = temp;}
}

2.2 堆排序

堆排序的思路:首先将存放在L[1...n]中的n个元素建成初始堆,因为堆本身的特点(以大顶堆为例),所以堆顶元素就是最大值。输出堆顶元素后,通常将堆底元素送入堆顶,此时根结点已不满足大顶堆的性质,堆被破坏,将堆顶元素向下调整使其继续保持大顶堆的性质,再输出堆顶元素。如此重复,直到堆中仅剩一个元素为止。需要注意的是排升序要建大堆,排降序建小堆

【堆排序算法的性能分析】

  • 空间效率:仅使用了常数个辅助单元,所以空间复杂度为O(1)
  • 时间效率:建堆时间为 O(n),之后有n-1次向下调整操作,每次调整的时间复杂度为 O(h),所以在最好、最坏和平均情况下,堆排序的时间复杂度为O(n\log_{2}n)
  • 稳定性:进行筛选时,有可能把后面相同关键字的元素调整到前面,所以堆排序算法是一种不稳定的排序算法。例如,表L = {1, 2, 2},构造初始堆时可能将2交换到堆顶,此时L = {2, 1, 2},最终排序序列为L = {1, 2, 2},显然,2与2的相对次序已发生变化。
  • 适用性:堆排序仅适用于顺序存储的线性表。
//堆排序
public static void heapSort(int[] array) {createHeap(array);int end = array.length-1;while (end > 0) {int tmp = array[0];array[0] = array[end];array[end] = tmp;siftDown(array,0,end);end--;}
}
//建大堆
private static void createHeap(int[] array) {int i = array.length/2-1;for (; i >= 0; i--){siftDown(array,i,array.length);}
}
//向下调整
private static void siftDown(int[] array, int parent, int len) {int child = parent*2 + 1;while (child < len){if(child+1 < len && array[child+1] > array[child]){child = child+1;}if(array[child] > array[parent]){int temp = array[child];array[child] = array[parent];array[parent] = temp;parent = child;child = parent*2 + 1;}else {break;}}
}                                                             

3. 交换排序

基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

3.1 冒泡排序

冒泡排序的基本思想是:从后往前(或从前往后)两两比较相邻元素的值,若为逆序(即 A[i-1] > A[1] ),则交换它们,直到序列比较完。我们称它为第一趟冒泡,结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置),关键字最小的元素如气泡一般逐渐往上“漂浮”至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时,前一趟确定的最小元素不再参与比较,每趟冒泡的结果是把序列中的最小元素(或最大元素)放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。排序过程如下:

  1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列,降序则反过来)。
  2. 从列表的开始一直到结尾,依次对每一对相邻元素都进行比较。这样,值最大的元素就通过交换“冒泡”到了列表的结尾,完成第一轮“冒泡”。
  3. 重复上一步,继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以,已经“冒泡”到后面的元素即使比较也不需要交换,不比较可以减少步骤)。
  4. 继续从列表开始进行比较,每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减,一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较),则列表排序完成。

//冒泡排序
public static void bubbleSort(int[] array){for (int i = 0; i < array.length; i++) {boolean flag = false;for (int j = 0; j < array.length-i-1; j++) {if(array[j] > array[j+1]){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;flag = true;}}if (!flag){break;}}
}

【冒泡排序算法的性能分析】

  • 空间效率:仅使用了常数个辅助单元,因而空间复杂度为O(1)
  • 时间效率:当初始序列有序时,显然第一趟冒泡后 flag 依然为 false (本趟没有元素交换),从而直接跳出循环,比较次数为 n-1,移动次数为 0,从而最好情况下的时间复杂度为O(n);当初始序列为逆序时,需要进行 n-1 趟排序,第 i 趟排序要进行 n-i 次关键字的比较,而且每次比较后都必须移动元素 3 次来交换元素位置。这种情况下,最坏情况下的时间复杂度为 O(n^{2}),平均时间复杂度为 O(n^{2})
  • 稳定性:由于 i > j 且 A[i] = A[j] 时,不会发生交换,因此冒泡排序是一种稳定的排序算法。
  • 适用性:冒泡排序适用于顺序存储链式存储的线性表。

3.2 快速排序

快速排序(以下有时简称快排)的基本思想是基于分治法的:在待排序表 L[1...n] 中任取一个元素 pivot 作为枢轴(或称基准,通常取首元素),通过一趟排序将待排序表划分为独立的两部分 L[1...k-1] 和 L[k+1...n],使得 L[1...k-1] 中的所有元素小于 pivot,L[k+1...n]中的所有元素大于或等于 pivot,则 pivot 放在了其最终位置L(k)上,这个过程称为一次划分。然后分别递归地对两个子表重复上述过程,直至每部分内只有一个元素或为空为止,即所有元素放在了其最终位置上。快速排序递归实现的主框架:

//快速排序                                                            
public static void quickSort(int[] array, int left, int right){   if(left >= right){                                            return;                                                   }                                                             int pivotpos = partition2(array,left,right);                  quickSort(array,left,pivotpos-1);                             quickSort(array,pivotpos+1,right);                            
}                                                                 

将区间按照基准值划分为左右两半部分的常见方式有:

3.2.1 Hoare版

排序过程:

  1. 选出一个key,一般是最左边或是最右边的。
  2. 定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
  3. 在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)。
  4. 此时key的左边都是小于key的数,key的右边都是大于key的数。
  5. 将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时待排序表已经有序。

//Hoare版
private static int partition(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}while (i < j && array[i] <= pivot) {i++;}  swap(array, i, j);}swap(array, i, left);return i;
}
3.2.2 挖坑法

排序过程:挖坑法思路与hoare版本(左右指针法)思路类似,不同之处在于把枢轴元素放在了一个变量中保存,直到一趟排序完后才把它放入到最终位置。

  1. 选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
  2. 定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)。
  3. 在走的过程中,若R遇到小于key的数,则停下,L开始走,直到L遇到一个大于key的数时,将L和R的内容交换,R再次开始走,如此进行下去,直到L和R最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)。
  4. 此时key的左边都是小于key的数,key的右边都是大于key的数。
  5. 将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时待排序表已经有序。

//挖坑法
private static int partition(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}array[i] = array[j];while (i < j && array[i] <= pivot) {i++;}array[j] = array[i];}array[i] = pivot;return i;
}
3.2.3 前后指针

排序过程:

  1. 选出一个key,一般是最左边或是最右边的。
  2. 起始时,prev指针指向序列开头,cur指针指向prev+1。
  3. 若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。
  4. 经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。
  5. 然后将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时待排序表已经有序。

写法一:

//前后指针法1
private static int partition(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;
}

写法二:

//前后指针法2
private static int partition(int[] array, int left, int right) {int d = left + 1;int pivot = array[left];for (int i = left + 1; i <= right; i++) {if (array[i] < pivot) {swap(array, i, d);d++;}}swap(array, d - 1, left);return d - 1;
}
3.2.4 快速排序优化
  1. 三数取中法选key。
  2. 递归到小的子区间时,可以考虑使用插入排序。
//快排的优化版
public static void quickSort1(int[] array,int left,int right) {if(left >= right) {return;}if(right - left + 1 == 7) {//使用直接插入排序进行排序insertSort2(array,left,right);return;}int index = midThreeNum(array,left,right);swap(array,left,index);//先划分int par = partition(array,left,right);quickSort1(array,left,par-1);quickSort1(array,par+1,right);
}
//快排中的直接插入
private static void insertSort2(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 {//array[j+1] = tmp;break;}}array[j+1] = tmp;}
}
//找到中位数的下标
private static int midThreeNum(int[] array,int start,int end) {int mid = (start + end) / 2;if(array[start] < array[end]) {if(array[mid] < array[start]) {return start;}else if(array[mid] > array[end]) {return end;}else {return mid;}}else {if(array[mid] >  array[start]) {return start;}else if(array[mid] <  array[end]) {return end;}else {return mid;}}
}
3.2.5 快速排序非递归
//快速排序非递归
void quickSortNonR(int[] a, int left, int right) {Stack<Integer> st = new Stack<>();st.push(left);st.push(right);while (!st.empty()) {right = st.pop();left = st.pop();if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基准值为分割点,形成左右两部分:[left, div) 和 [div+1, right)st.push(div+1);st.push(right);  st.push(left);st.push(div);}
}

【快速排序算法的性能分析】

  • 空间效率:由于快速排序是递归的,因此需要借助一个递归工作栈来保存每层递归调用的必要信息,其容量与递归调用的最大层数一致。最好情况下为 O(\log_{2}n);最坏情况下,要进行n-1次递归调用,因此栈的深度为 O(n);平均情况下,栈的深度为 O(\log_{2}n)
  • 时间效率:快速排序的运行时间与划分是否对称有关,快速排序的最坏情况发生在两个区域分别包含 n-1个元素和 0 个元素时,这种最大限度的不对称性若发生在每层递归上,即对应于初始排序表基本有序或基本逆序时,就得到最坏情况下的时间复杂度为O(n^{2})。有很多方法可以提高算法的效率:一种方法是尽量选取一个可以将数据中分的枢轴元素,如从序列的头尾及中间选取三个元素,再取这三个元素的中间值作为最终的枢轴元素;或者随机地从当前表中选取枢轴元素,这样做可使得最坏情况在实际排序中几乎不会发生。在最理想的状态下,即 Partition()能做到最平衡的划分,得到的两个子问题的大小都不可能大于 n/2,在这种情况下,快速排序的运行速度将大大提升,此时,时间复杂度为 O(n\log_{2}n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近,而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

  • 稳定性:在划分算法中,若右端区间有两个关键字相同,且均小于基准值的记录,则在交换到左端区间后,它们的相对位置会发生变化,即快速排序是一种不稳定的排序算法。例如,表 L = {3, 2, 2},经过一趟排序后 L = {2, 2, 3},最终排序序列也是L = {2, 2, 3},显然,2与2的相对次序已发生了变化。
  • 适用性:快速排序仅适用于顺序存储的线性表。

4. 归并排序

基本思想:归并的含义是将两个或两个以上的有序表合并成一个新的有序表。假定待排序表含有 n 个记录,则可将其视为 n 个有序的子表,每个子表的长度为1,然后两两归并,得到 n/2 (向上取整) 个长度为 2 或 1 的有序表;继续两两归并……如此重复,直到合并成一个长度为 n 的有序表为止,这种排序算法称为二路归并排序。归并排序过程如下:

//归并排序
public static void mergeSort(int[] array,int left,int right){if(left == right){return;}int mid = (left+right)/2;mergeSort(array,left,mid);mergeSort(array,mid+1,right);merge(array,left,mid,right);
}
private static void merge(int[] array, int left, int mid, int right) {int[] tempArr = new int[right-left+1];int s1 = left;int s2 = mid+1;int k = 0;while (s1 <= mid && s2 <= right){if(array[s1] < array[s2]){tempArr[k++] = array[s1++];}else {tempArr[k++] = array[s2++];}}while (s1 <= mid){tempArr[k++] = array[s1++];}while (s2 <= right){tempArr[k++] = array[s2++];}for (int i = 0; i < tempArr.length; i++) {array[i+left] = tempArr[i];}
}

【归并排序算法的性能分析】

  • 空间效率:Merge() 操作中,辅助空间刚好为n个单元,因此算法的空间复杂度为 O(n)
  • 时间效率:每趟归并的时间复杂度为 O(n),共需进行 \log_{2}n (向上取整) 趟归并,因此算法的时间复杂度为 O(n\log_{2}n)
  • 稳定性:由于 Merge() 操作不会改变相同关键字记录的相对次序,因此二路归并排序算法是一种稳定的排序算法。
  • 适用性:归并排序适用于顺序存储链式存储的线性表。

5. 基数排序(了解)

基本思想:基数排序与前面的排序算法不一样,它不基于比较和移动元素来进行排序,而是基于多关键字排序的思想,将一个逻辑关键字分为多个关键字,它是基于关键字各位的大小进行排序的。基数排序有两种实现方式:第一种是最高位优先(MSD)法,按关键字位权重递减依次逐层划分成若干更小的子序列,最后将所有子序列依次连接成一个有序序列;第二种是最低位优先(LSD)法,按关键字位权重递增依次进行排序,最后形成一个有序序列。

最低位优先法排序过程:

  1. 将待排序数字做如下处理,按最低位优先原则(也就是个位开始),依次将数字放入“桶”中。
  2. 将“桶中的数据”按从小到大的顺序依次拿出,若桶中有多个数据,则按照先进先出的原则拿出数据并排放好。
  3. 个位排完后,下面十位,百位,千位…的方法和个位一样(低位优先)。注:没有高位的全部以0代替,如:7的百位和十位为0。

例如,通过最低位优先法,对给定的关键字序列{110,119,007,911,114,120,122}进行排序:

1. 该序列的链式结构如下:

2. 首先按照关键字的个位数字大小进行第一趟基数排序:

3. 根据第一趟的顺序,按照关键字的十位数字大小进行第二趟基数排序:

4. 根据第二趟的顺序,按照关键字的百位数字大小进行第三趟基数排序:

5. 通过最低位优先法,得到排好的序列为{007,110,114,119,120,122,911}。

【基数排序算法的性能分析】

  • 空间效率:一趟排序需要的辅助存储空间为 r (r个队列:r 个队头指针和 r 个队尾指针),但以后的排序中会重复使用这些队列,所以基数排序的空间复杂度为O(r)
  • 时间效率:基数排序需要进行 d 趟“分配”和“收集”操作。一趟分配需要遍历所有关键字,时间复杂度为 O(n);一趟收集需要合并 r 个队列,时间复杂度为 O(r)。因此基数排序的时间复杂度为 O(d(n+r)),它与序列的初始状态无关。
  • 稳定性:每一趟分配和收集都是从前往后进行的,不会交换相同关键字的相对位置,因此基数排序是一种稳定的排序算法。
  • 适用性:基数排序适用于顺序存储链式存储的线性表。

海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G,需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每个 512M。
  2. 分别对 512M 排序,因为内存已经可以放的下,所以任意排序方式都可以。
  3. 进行 2 路归并,同时对 200 份有序文件做归并过程,最终结果就有序了。

6. 计数排序(了解)

基本思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。排序过程:

  1. 统计相同元素出现次数。
  2. 根据统计的结果将序列回收到原来的序列中。

//计数排序
public static void countSort(int[] array) {//1. 求最大值 和 最小值 来确定 计数数组的大小 len//O(N)int max = array[0];int min = array[0];for (int i = 1; i < array.length; i++) {if(max < array[i]) {max = array[i];}if(min > array[i]) {min = array[i];}}int len = max - min + 1;int[] count = new int[len];//2.遍历原来的数组 存放元素到计数数组当中//O(N)for (int i = 0; i < array.length; i++) {int index = array[i]-min;count[index]++;}//3. 遍历计数数组//O(范围)int arrIndex = 0;for (int i = 0; i < count.length; i++) {while (count[i] != 0) {array[arrIndex] = i+min;arrIndex++;count[i]--;}}
}

【计数排序算法的性能总结】

  • 空间效率:计数排序是一种用空间换时间的做法。输出数组的长度为 n;辅助的计数数组的长度为 k,空间复杂度为 O(n+k)。若不把输出数组视为辅助空间,则空间复杂度为 O(k)
  • 时间效率:上述代码的第1个和第3个 for 循环所花的时间为 O(k),第2个和第4个 for 循环所花的时间为 O(n),总时间复杂度为 O(n+k)。因此,当 k=O(n) 时,计数排序的时间复杂度为O(n);但当 k>O(n\log_{}n)时,其效率反而不如一些基于比较的排序(如快速排序、堆排序等)。
  • 稳定性:上述代码的第4个 for 循环从后往前遍历输入数组,相同元素在输出数组中的相对位置不会改变,因此计数排序是一种稳定的排序算法。
  • 适用性:计数排序更适用于顺序存储的线性表。计数排序适用于序列中的元素是整数且元素范围 (0 ~ k-1) 不能太大,否则会造成辅助空间的浪费。

7. 桶排序(了解)

三、各种排序算法的比较及应用

1. 内部排序算法的比较

1.1 时间复杂度

简单选择排序直接插入排序冒泡排序平均情况下的时间复杂度都为 O(n^{2}),且实现过程也较为简单,但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O(n),而简单选择排序则与序列的初始状态无关。希尔排序作为插入排序的拓展,对较大规模的数据都可以达到很高的效率,但目前未得出其精确的渐近时间。堆排序利用了一种称为堆的数据结构,可以在线性时间内完成建堆,且在 O(n\log_{2}n)内完成排序过程。快速排序基于分治的思想,虽然最坏情况下的时间复杂度会达到 O(n^{2}),但快速排序的平均性能可以达到 O(n\log_{2}n),在实际应用中常常优于其他排序算法。归并排序同样基于分治的思想,但由于其分割子序列与初始序列的排列无关,因此它的最好、最坏和平均时间复杂度均为 O(n\log_{2}n)

1.2 空间复杂度

简单选择排序插入排序冒泡排序希尔排序堆排序都仅需借助常数个辅助空间,因此空间复杂度为 O(1)快速排序需要借助一个递归工作栈,平均大小为 O(\log_{2}n),当然在最坏情况下可能会增长到 O(n)二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制,大小为 O(n),虽然有方法能克服这个缺点,但其代价是算法会很复杂而且时间复杂度会增加。

1.3 稳定性

插入排序、冒泡排序、归并排序和基数排序稳定的排序算法,而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序算法。

1.4 适用性

折半插入排序、希尔排序、快速排序和堆排序适用于顺序存储。直接插入排序、冒泡排序、简单选择排序、归并排序和基数排序既适用于顺序存储,又适用于链式存储

各种排序算法的性质
各种排序算法的性质

2. 内部排序算法的应用

通常情况,对排序算法的比较和应用应考虑以下情况。

2.1 选取排序算法需要考虑的因素

  1. 待排序的元素个数 n。
  2. 待排序的元素的初始状态。
  3. 关键字的结构及其分布情况。
  4. 稳定性的要求。
  5. 存储结构及辅助空间的大小限制等。

2.2 排序算法小结

  1. 若n较小,可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多,因此当记录本身信息量较大时,用简单选择排序较好。
  2. 若n较大,应采用时间复杂度为 O(n\log_{2}n)的排序算法:快速排序、堆排序或归并排序。当待排序的关键字随机分布时,快速排序被认为是目前基于比较的内部排序算法中最好的算法。堆排序所需的辅助空间少于快速排序,且不会出现快速排序可能的最坏情况,这两种排序都是不稳定的。若要求稳定且时间复杂度为 O(n\log_{2}n),可选用归并排序。
  3. 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
  4. 在基于比较的排序算法中,每次比较两个关键字的大小之后,仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关键字随机分布时,任何借助于“比较”的排序算法,至少需要 O(n\log_{2}n)的时间。
  5. 若n很大,记录的关键字位数较少且可以分解时,采用基数排序较好。
  6. 当记录本身信息量较大时,为避免耗费大量时间移动记录,可用链表作为存储结构。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/431219.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无人机之编程基础原理

无人机编程基础原理涉及多个方面&#xff0c;主要包括无人机的基本原理、飞行控制算法、编程语言及算法应用等。以下是对这些方面的详细阐述&#xff1a; 一、无人机基本原理 无人机的基本原理是理解其结构、飞行原理、传感器和控制系统等的基础。无人机通常由机身、动力系统&…

企业如何利用短视频平台做口碑塑造和品牌营销?

抖音和小红书作为短视频平台的代表&#xff0c;吸引了大量的用户和品牌。如何利用抖音、小红书等短视频平台进行品牌塑造和口碑营销呢&#xff1f;小马识途营销顾问分析&#xff0c;短视频平台的用户以年轻人为主&#xff0c;他们具有高度的社交性和消费意愿。短视频平台提供了…

fiddler抓包11_列表显示服务器IP (配置文件)

请求列表默认不显示服务器IP字段&#xff0c;也无法从定制列窗口添加&#xff0c;可以修改CustomRules.js实现。 ① 菜单栏“Rules”&#xff08;规则&#xff09; - “Customize Rules...”&#xff08;自定义规则&#xff09;&#xff0c;打开CustomRules.js文件。 &#xf…

Qt (17)【Qt 文件操作 读写保存】

阅读导航 引言一、Qt文件概述二、输入输出设备类三、文件读写类四、文件和目录信息类五、自定义“记事本” 引言 在上一篇文章中&#xff0c;我们学习了Qt的事件处理机制&#xff0c;知道了如何响应用户的操作。但应用程序常常还需要处理文件&#xff0c;比如读写数据。所以&a…

CVPR最牛图像评价算法!

本文所涉及所有资源均在 传知代码平台可获取。 目录 概述 一、论文思路 1.多任务学习框架&#xff1a; 2.视觉-语言对应关系&#xff1a; 3.动态损失权重&#xff1a; 4.模型优化和评估&#xff1a; 二、模型介绍 三、详细实现方法 1.图像编码器和语言编码器&#xff08;Image…

大语言模型的发展-OPENBMB

一、自然语言处理的基础 1、图灵测试 就是验证人工智能程序有多智能 让计算机像人一样&#xff0c;能够听懂问题&#xff0c;然后给出答案&#xff1b; 自然语言发展历史&#xff1a; advances in Natural Lannguage Processing --论文 2、自然语言处理的基本任务和应用 …

MES系统如何提升制造企业的运营效率和灵活性

参考拓展&#xff1a;苏州稳联-西门子MES系统-赋能智能制造的核心引擎 制造执行系统(MES)在提升制造企业运营效率和灵活性方面发挥着关键作用。 一、MES系统的基本概念和功能 MES系统是连接企业管理层与生产现场的重要桥梁。它主要负责生产调度、资源管理、质量控制等多个方…

【重学 MySQL】三十一、字符串函数

【重学 MySQL】三十一、字符串函数 函数名称用法描述ASCII(S)返回字符串S中的第一个字符的ASCII码值CHAR_LENGTH(s)返回字符串s的字符数&#xff0c;与CHARACTER_LENGTH(s)相同LENGTH(s)返回字符串s的字节数&#xff0c;和字符集有关CONCAT(s1,s2,…,sn)连接s1,s2,…,sn为一个字…

低代码可视化工具--vue条件判断v-if可视化设置-代码生成器

在Vue UniApp中&#xff0c;条件判断通常是通过指令v-if、v-else-if、v-else来实现的。这些机制允许你根据表达式的真假值来决定是否渲染某个元素或元素组&#xff0c;或者执行特定的逻辑。 条件判断说明 v-if 是惰性的&#xff1a;如果在初始渲染时条件为假&#xff0c;则什么…

如何使用ssm实现基于Java web的高校学生课堂考勤系统的设计与实现+vue

TOC ssm686基于Java web的高校学生课堂考勤系统的设计与实现vue 第一章 课题背景及研究内容 1.1 课题背景 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#x…

BUUCTF [SCTF2019]电单车详解两种方法(python实现绝对原创)

使用audacity打开&#xff0c;发现是一段PT2242 信号 PT2242信号 有长有短&#xff0c;短的为0&#xff0c;长的为1化出来 这应该是截获电动车钥匙发射出的锁车信号 0 01110100101010100110 0010 0前四位为同步码0 。。。中间这20位为01110100101010100110为地址码0010为功…

Leetcode 反转链表

使用递归 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/ class S…

Java基础知识扫盲

目录 Arrays.sort的底层实现 BigDecimal(double)和BigDecimal(String)有什么区别 Char可以存储一个汉字吗 Java中的Timer定时调度任务是咋实现的 Java中的序列化机制是咋实现的 Java中的注解是干嘛的 Arrays.sort的底层实现 Arrays.sort是Java中提供的对数组进行排序的…

动态规划11,完全背包模板

NC309 完全背包 问题一&#xff1a;求这个背包至多能装多大价值的物品&#xff1f; 状态表示&#xff1a;经验题目要求 dp[i][j] 表示 从前i个物品中挑选&#xff0c;总体积不超过j&#xff0c;所有选法中&#xff0c;能选出来的最大价值。 状态转移方程 根据最后一步的状态&a…

harmonyOS ArkTS最新跳转Navigation

文章目录 取消标题栏初始页面(load)设置为竖屏 自定义标题Tabs&TabContentTabs通过divider实现了分割线各种属性 图片下载 官方文档 Entry Component struct Index {State message: string Hello WorldState djs:number 5build() {Column(){Navigation(){}.title("g…

达梦-华为鲲鹏ARM架构下性能测试最佳实践

一、测试综述 1.1 测试目的 本次测试的目的是验证达梦数据库&#xff0c;在鲲鹏服务器下&#xff0c;不同服务器参数基于sysbench性能压力测试的表现。本次参数是根据为华为鲲鹏arm服务器调优十板斧内建议值调整 成长地图-鲲鹏开发套件开发文档-鲲鹏社区 1.2 通用指标 指标…

基于STM32的点滴输液报警器-设计说明书

设计摘要&#xff1a; 本文介绍了基于STM32微控制器的点滴输液报警器的设计与实现。点滴输液是医疗领域中常见的治疗方式&#xff0c;但输液速度的控制对患者的安全和治疗效果至关重要。因此&#xff0c;设计一种能够监测输液速度并在异常情况下发出警报的系统显得十分必要。基…

吴恩达深度学习笔记:卷积神经网络(Foundations of Convolutional Neural Networks)2.3-2.4

目录 第四门课 卷积神经网络&#xff08;Convolutional Neural Networks&#xff09;第二周 深度卷积网络&#xff1a;实例探究&#xff08;Deep convolutional models: case studies&#xff09;2.3 残差网络(ResNets)(Residual Networks (ResNets))2.4 残差网络为什么有用&am…

JavaEE: 深入探索TCP网络编程的奇妙世界(一)

文章目录 TCPTCP协议段落格式TCP相关机制TCP核心机制一: 确认应答32位序号32位确认序号后发先至问题 TCP TCP要比UDP更复杂一些~ TCP的全称为"传输控制协议".他负责对数据的传输进行一个详细的控制. TCP协议段落格式 源/目的端口号: 表示数据是从哪个进程来.到哪个…

Python 如何处理大文件的读取

Python 如何处理大文件的读取 在日常的开发工作中&#xff0c;我们经常会遇到处理大文件的需求。无论是读取日志文件、处理数据集&#xff0c;还是分析超大文本文件&#xff0c;大文件操作都是一个非常常见的挑战。尤其是在内存有限的环境中&#xff0c;直接将整个文件加载到内…