如何快速编写与优化快速排序算法的代码实例
参考资料
快速排序算法的编码描述
快排的基本思路
- 先通过第一趟排序,将数组原地划分为两部分,其中一部分的所有数据都小于另一部分的所有数据。原数组被划分为2份
- 通过递归的处理, 再对原数组分割的两部分分别划分为两部分,同样是使得其中一部分的所有数据都小于另一部分的所有数据。 这个时候原数组被划分为了4份
- 就1,2被划分后的最小单元子数组来看,它们仍然是无序的,但是! 它们所组成的原数组却逐渐向有序的方向前进。
- 到最后, 数组被划分为多个由一个元素或多个相同元素组成的单元, 这时候整个数组就有序了
3 1 4 1 5 9 2 6 5 3
1 1 2 3 3 4 5 5 6
快排的实现步骤
下面我就只讲解1和2步骤, 而在1,2中,关键在于如何实现“划分”
切分的关键点: 基准元素, 左游标和右游标
划分的过程有三个关键点:“基准元素”, “左游标” 和“右游标”。
- 基准元素:它是将数组划分为两个子数组的过程中, 用于界定大小的值, 以它为判断标准, 将小于它的数组元素“划分”到一个“小数值数组”里, 而将大于它的数组元素“划分”到一个“大数值数组”里面。这样,我们就将数组分割为两个子数组, 而其中一个子数组里的元素恒小于另一个子数组里的元素
- 左游标: 它一开始指向待分割数组最左侧的数组元素。在排序过程中,它将向右移动
- 右游标: 它一开始指向待分割数组最右侧的数组元素。在排序过程中,它将向左移动
一趟切分的具体过程
- “基准元素v是怎么选的?”
- 游标i,j的移动的过程中发生了什么事情(比如元素交换)?,
- 为什么左右游标相遇时一趟切分就完成了?
- 左游标向右扫描, 跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素, 在那个位置停下。
- 右游标向左扫描, 跨过所有大于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素,在那个位置停下
- 左右游标没有相遇
- 左右游标相遇了
【注意】这里你可能会问: 在我们制定的规则里, 左游标先扫描和右游标先扫描有区别吗? (如果你这样想的话就和我想到一块去了...嘿嘿),因为就上图而言,两种情况下一趟排序中两个游标相遇的位置是不同的(一般而言,除非相遇位置的下方的元素刚好和基准元素相同):
- 如果右游标先扫描,左右游标相遇的位置应该是3上方(图示)
- 但如果左游标先扫描, 左右游标相遇的位置却是9上方
6 1 2 5 4 3 9 7 10 8
1 2 5 4 3 6 9 7 10 8
总结一趟排序的过程
快速排序代码展示
具体的代码
// 交换两个数组元素 private static void exchange(int [] a , int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
private static int partition (int[] a, int low, int high) { int i = low, j = high+1; // i, j为左右扫描指针 PS: 思考下为什么j比i 多加一个1呢? int pivotkey = a[low]; // pivotkey 为选取的基准元素(头元素) while(true) { while (a[--j]>pivotkey) { if(j == low) break; } // 右游标左移 while(a[++i]<pivotkey) { if(i == high) break; } // 左游标右移 if(i>=j) break; // 左右游标相遇时候停止, 所以跳出外部while循环 else exchange(a,i, j) ; // 左右游标未相遇时停止, 交换各自所指元素,循环继续 } exchange(a, low, j); // 基准元素和游标相遇时所指元素交换,为最后一次交换 return j; // 一趟排序完成, 返回基准元素位置 }
private static void sort (int [] a, int low, int high) { if(high<= low) { return; } // 终止递归 int j = partition(a, low, high); // 调用partition进行切分 sort(a, low, j-1); // 对上一轮排序(切分)时,基准元素左边的子数组进行递归 sort(a, j+1, high); // 对上一轮排序(切分)时,基准元素右边的子数组进行递归 }
对切分函数partition的解读
while (a[--j]>pivotkey) { ... }
先将右游标左移一位,然后判断指向的数组元素和基准元素pivotkey比较大小, 如果该元素大于基准元素, 那么循环继续,j再次减1,右游标再次左移一位...... (循环体可以看作是空的)
if(i>=j) break;
从i < j到 i == j 代表了“游标未相遇”到“游标相遇”的过度过程,此时跳出外部循环, 切分已接近完成,紧接着通过 exchange(a, low, j) 交换基准元素和相遇游标所指元素的位置, low是基准元素的位置(头部元素), j是当前两个游标相遇的位置
while (a[--j]>pivotkey) { if(j == low) break; } // 右游标左移
中,当随着右游标左移,到j = low + 1的时候,有 a[--j] == pivotkey为true(两者都是基准元素),自动跳出了while循环,所以就不需要在循环体里再判断 j == low 了
int i = low, j = high+1
结合下面两个While循环中的判断条件:
while (a[--j]>pivotkey) { ... } while (a[++i]<pivotkey) { ... }
可知道, 左游标 i 第一次自增的时候, 跳过了对基准元素 a[low] 所执行的 a[low] < pivotkey判断, 这是因为在我们当前的算法方案里,基准元素和左游标初始所指的元素是同一个,所以没有执行a[low]>pivotke这个判断的必要。所以跳过( 一开始a[low] == pivotkey,如果执行判断那么一开始就会跳出内While循环,这显然不是我们希望看到的)
对主体函数sort的解读
sort(a, low, j-1); sort(a, j+1, high);
进行下一轮递归,设置j -1 和j + 1 是因为上一轮基准元素的位置已经是有序的了,不要再纳入下一轮递归里
public class QuickSort { // 交换两个数组元素 private static void exchange(int [] a , int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } private static int partition (int[] a, int low, int high) { int i = low, j = high+1; // i, j为左右扫描指针 PS: 思考下为什么j比i 多加一个1呢? int pivotkey = a[low]; // pivotkey 为选取的基准元素(头元素) while(true) { while (a[--j]>pivotkey) { if(j == low) break; } // 右游标左移 while(a[++i]<pivotkey) { if(i == high) break; } // 左游标右移 if(i>=j) break; // 左右游标相遇时候停止, 所以跳出外部while循环 else exchange(a,i, j) ; // 左右游标未相遇时停止, 交换各自所指元素,循环继续 } exchange(a, low, j); // 基准元素和游标相遇时所指元素交换,为最后一次交换 return j; // 一趟排序完成, 返回基准元素位置 } private static void sort (int [] a, int low, int high) { if(high<= low) { return; } // 当high == low, 此时已是单元素子数组,自然有序, 故终止递归 int j = partition(a, low, high); // 调用partition进行切分 sort(a, low, j-1); // 对上一轮排序(切分)时,基准元素左边的子数组进行递归 sort(a, j+1, high); // 对上一轮排序(切分)时,基准元素右边的子数组进行递归 } public static void sort (int [] a){ //sort函数重载, 只向外暴露一个数组参数 sort(a, 0, a.length - 1); } }
public class Test { public static void main (String [] args) { int [] array = {4,1,5,9,2,6,5,6,1,8,0,7 }; QuickSort.sort(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i]); } } }
01124556789
优化点一 —— 切换到插入排序
if(high<= low) { return; }
if(high<= low + M) { Insertion.sort(a,low, high) return; } // Insertion表示一个插入排序类
private static void sort (int [] a, int low, int high) { if(high<= low + 10) { Insertion.sort(a,low, high) return; } // Insertion表示一个插入排序类 int j = partition(a, low, high); // 调用partition进行切分 sort(a, low, j-1); // 对上一轮排序(切分)时,基准元素左边的子数组进行递归 sort(a, j+1, high); // 对上一轮排序(切分)时,基准元素右边的子数组进行递归 }
优化点二 —— 基准元素选取的随机化
- 排序前打乱数组的顺序
- 通过随机数保证取得的基准元素的随机性
- 三数取中法取得基准元素(推荐)
public static void sort (int [] a){ StdRandom.shuffle(a) // 外部导入的乱序算法,打乱数组的分布 sort(a, 0, a.length - 1); }
private static int getRandom (int []a, int low, int high) { int RdIndex = (int) (low + Math.random()* (high - low)); // 随机取出其中一个数组元素的下标 exchange(a, RdIndex, low); // 将其和最左边的元素互换 return a[low]; } private static int partition (int[] a, int low, int high) { int i = low, j = high+1; // i, j为左右扫描指针 PS: 思考下为什么j比i 多加一个1呢? int pivotkey = getRandom (a, low, high); // 基准元素随机化 while(true) { while (a[--j]>pivotkey) { if(j == low) break; } // 右游标左移 while(a[++i]<pivotkey) { if(i == high) break; } // 左游标右移 if(i>=j) break; // 左右游标相遇时候停止, 所以跳出外部while循环 else exchange(a,i, j) ; // 左右游标未相遇时停止, 交换各自所指元素,循环继续 } exchange(a, low, j); // 基准元素和游标相遇时所指元素交换,为最后一次交换 return j; // 一趟排序完成, 返回基准元素位置 }
package mypackage; public class QuickSort { // 交换两个数组元素 private static void exchange(int [] a , int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } // 选取左中右三个元素,求出中位数, 放入数组最左边的a[low]中 private static int selectMiddleOfThree(int[] a, int low, int high) { int middle = low + (high - low)/2; // 取得位于数组
上一篇: 四款改进快速排序的方法
下一篇: 10种简单高效提升网页速度的方法
推荐阅读
-
如何快速编写与优化快速排序算法的代码实例
-
MAX_LEN) {
int pivot = partition(arr, left, right);
quicksort_optimized(arr, left, pivot - 1);
quicksort_optimized(arr, pivot + 1, right);
} else {
// 使用插入排序处理小数组
}
}
```
- 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如:
原序列: 1 4 6 7 6 6 7 6 8 6
- 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6
- 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6
- 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7
- 下次划分得到的子序列:1 4 和 7 8 7
通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。">
改进版快速排序:针对部分有序列的策略与优化技巧" - 随机选枢轴:当数据部分有序时,传统快速排序通过固定枢轴可能导致效率低下。为此,我们采用随机选取枢轴的方法,代码如下: ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换:针对小且部分有序的数组,快速排序不如插入排序高效。因此,当待排序序列长度小于等于10时,我们会切换至插入排序: ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (length > MAX_LEN) { int pivot = partition(arr, left, right); quicksort_optimized(arr, left, pivot - 1); quicksort_optimized(arr, pivot + 1, right); } else { // 使用插入排序处理小数组 } } ``` - 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如: 原序列: 1 4 6 7 6 6 7 6 8 6 - 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6 - 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6 - 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7 - 下次划分得到的子序列:1 4 和 7 8 7 通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。