排序法的优缺点（各种排序法的优劣）

本文目录

• 各种排序法的优劣
• 排序法的缺点有
• 求各排序方法的特点
• 数据库VF中排序与索引相比各有什么优缺点
• 荷兰提出的单元危险快速排序法有何优点
• 排序法的排序法的分类

各种排序法的优劣

明显，快速排序速度最快，属于不稳定排序，所谓不稳定就是 序列中如果有相同元素， 排序后 相同元素的相对位置可能会发生变化，比如序列中有2个5，排序后可能后面的5排在前面，这个影响不大。
插入排序 和冒泡的时间复杂度是一样的，O(n^2)，冒泡没什么好说的，插入排序主要用于序列基本有序的情况，此时时间复杂度会大大降低

排序法的缺点有

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

求各排序方法的特点

看一下下面代码 希望对你有所帮助
import java.util.Random;

/**
* 排序测试类
*
* 排序算法的分类如下：
* 1.插入排序（直接插入排序、折半插入排序、希尔排序）；
* 2.交换排序（冒泡泡排序、快速排序）；
* 3.选择排序（直接选择排序、堆排序）；
* 4.归并排序；
* 5.基数排序。
*
* 关于排序方法的选择：
* (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
* 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
* (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
* (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
*
* @author WangRuifeng
*/
public class SortTest {

/**
* 初始化测试数组的方法
* @return 一个初始化好的数组
*/
public int createArray() {
Random random = new Random();
int array = new int;
for (int i = 0; i 《 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100);//生成两个随机数相减，保证生成的数中有负数
}
System.out.println(“==========原始序列==========“);
printArray(array);
return array;
}

/**
* 打印数组中的元素到控制台
* @param source
*/
public void printArray(int source) {
for (int i : source) {
System.out.print(i + “ “);
}
System.out.println();
}

/**
* 交换数组中指定的两元素的位置
* @param source
* @param x
* @param y
*/
private void swap(int source, int x, int y) {
int temp = source[x];
source[x] = source[y];
source[y] = temp;
}

/**
* 冒泡排序----交换排序的一种
* 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
* 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
*
* @param source 要排序的数组
* @param sortType 排序类型
* @return
*/
public void bubbleSort(int source, String sortType) {
if (sortType.equals(“asc“)) { //正排序，从小排到大
for (int i = source.length - 1; i 》 0; i--) {
for (int j = 0; j 《 i; j++) {
if (source[j] 》 source[j + 1]) {
swap(source, j, j + 1);
}
}
}
} else if (sortType.equals(“desc“)) { //倒排序，从大排到小
for (int i = source.length - 1; i 》 0; i--) {
for (int j = 0; j 《 i; j++) {
if (source[j] 《 source[j + 1]) {
swap(source, j, j + 1);
}
}
}
} else {
System.out.println(“您输入的排序类型错误！“);
}
printArray(source);//输出冒泡排序后的数组值
}

/**
* 直接选择排序法----选择排序的一种
* 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
* 性能：比较次数O(n^2),n^2/2
* 交换次数O(n),n
* 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
* 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
*
* @param source 要排序的数组
* @param sortType 排序类型
* @return
*/
public void selectSort(int source, String sortType) {

if (sortType.equals(“asc“)) { //正排序，从小排到大
for (int i = 0; i 《 source.length; i++) {
for (int j = i + 1; j 《 source.length; j++) {
if (source[i] 》 source[j]) {
swap(source, i, j);
}
}
}
} else if (sortType.equals(“desc“)) { //倒排序，从大排到小
for (int i = 0; i 《 source.length; i++) {
for (int j = i + 1; j 《 source.length; j++) {
if (source[i] 《 source[j]) {
swap(source, i, j);
}
}
}
} else {
System.out.println(“您输入的排序类型错误！“);
}
printArray(source);//输出直接选择排序后的数组值
}

/**
* 插入排序
* 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。
* 性能：比较次数O(n^2),n^2/4
* 复制次数O(n),n^2/4
* 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
*
* @param source 要排序的数组
* @param sortType 排序类型
*/
public void insertSort(int source, String sortType) {
if (sortType.equals(“asc“)) { //正排序，从小排到大
for (int i = 1; i 《 source.length; i++) {
for (int j = i; (j 》 0) && (source[j] 《 source[j - 1]); j--) {
swap(source, j, j - 1);
}
}
} else if (sortType.equals(“desc“)) { //倒排序，从大排到小
for (int i = 1; i 《 source.length; i++) {
for (int j = i; (j 》 0) && (source[j] 》 source[j - 1]); j--) {
swap(source, j, j - 1);
}
}
} else {
System.out.println(“您输入的排序类型错误！“);
}
printArray(source);//输出插入排序后的数组值
}

/**
* 反转数组的方法
* @param source 源数组
*/
public void reverse(int source) {

int length = source.length;
int temp = 0;//临时变量

for (int i = 0; i 《 length / 2; i++) {
temp = source[i];
source[i] = source[length - 1 - i];
source[length - 1 - i] = temp;
}
printArray(source);//输出到转后数组的值
}

/**
* 快速排序
* 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
* 步骤为：
* 1. 从数列中挑出一个元素，称为 “基准“（pivot），
* 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
* 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
* @param source 待排序的数组
* @param low
* @param high
* @see SortTest#qsort(int, int, int)
* @see SortTest#qsort_desc(int, int, int)
*/
public void quickSort(int source, String sortType) {
if (sortType.equals(“asc“)) { //正排序，从小排到大
qsort_asc(source, 0, source.length - 1);
} else if (sortType.equals(“desc“)) { //倒排序，从大排到小
qsort_desc(source, 0, source.length - 1);
} else {
System.out.println(“您输入的排序类型错误！“);
}
}

/**
* 快速排序的具体实现，排正序
* @param source
* @param low
* @param high
*/
private void qsort_asc(int source, int low, int high) {
int i, j, x;
if (low 《 high) { //这个条件用来结束递归
i = low;
j = high;
x = source[i];
while (i 《 j) {
while (i 《 j && source[j] 》 x) {
j--; //从右向左找第一个小于x的数
}
if (i 《 j) {
source[i] = source[j];
i++;
}
while (i 《 j && source[i] 《 x) {
i++; //从左向右找第一个大于x的数
}
if (i 《 j) {
source[j] = source[i];
j--;
}
}
source[i] = x;
qsort_asc(source, low, i - 1);
qsort_asc(source, i + 1, high);
}
}

/**
* 快速排序的具体实现，排倒序
* @param source
* @param low
* @param high
*/
private void qsort_desc(int source, int low, int high) {
int i, j, x;
if (low 《 high) { //这个条件用来结束递归
i = low;
j = high;
x = source[i];
while (i 《 j) {
while (i 《 j && source[j] 《 x) {
j--; //从右向左找第一个小于x的数
}
if (i 《 j) {
source[i] = source[j];
i++;
}
while (i 《 j && source[i] 》 x) {
i++; //从左向右找第一个大于x的数
}
if (i 《 j) {
source[j] = source[i];
j--;
}
}
source[i] = x;
qsort_desc(source, low, i - 1);
qsort_desc(source, i + 1, high);
}
}

/**
* 二分法查找
* 查找线性表必须是有序列表
*
* @param source
* @param key
* @return
*/
public int binarySearch(int source, int key) {
int low = 0, high = source.length - 1, mid;
while (low 《= high) {
mid = (low + high) 》》》 1; //相当于mid = (low + high) / 2，但是效率会高些
if (key == source[mid]) {
return mid;
} else if (key 《 source[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}

public static void main(String args) {
SortTest sortTest = new SortTest();

int array = sortTest.createArray();

System.out.println(“==========冒泡排序后(正序)==========“);
sortTest.bubbleSort(array, “asc“);
System.out.println(“==========冒泡排序后(倒序)==========“);
sortTest.bubbleSort(array, “desc“);

array = sortTest.createArray();

System.out.println(“==========倒转数组后==========“);
sortTest.reverse(array);

array = sortTest.createArray();

System.out.println(“==========选择排序后(正序)==========“);
sortTest.selectSort(array, “asc“);
System.out.println(“==========选择排序后(倒序)==========“);
sortTest.selectSort(array, “desc“);

array = sortTest.createArray();

System.out.println(“==========插入排序后(正序)==========“);
sortTest.insertSort(array, “asc“);
System.out.println(“==========插入排序后(倒序)==========“);
sortTest.insertSort(array, “desc“);

array = sortTest.createArray();
System.out.println(“==========快速排序后(正序)==========“);
sortTest.quickSort(array, “asc“);
sortTest.printArray(array);
System.out.println(“==========快速排序后(倒序)==========“);
sortTest.quickSort(array, “desc“);
sortTest.printArray(array);

System.out.println(“==========数组二分查找==========“);
System.out.println(“您要找的数在第“ + sortTest.binarySearch(array, 74) + “个位子。（下标从0计算）“);
}
}

数据库VF中排序与索引相比各有什么优缺点

一般使用索引，索引可以建立多个，想用哪个用哪个，特别是当数据特别多、特别大的情况下，排序一次需要很多时间，而索引就非常快速。
补充：
可以这样说，现在的数据库都没有排序的的概念，排序是早期FOXBASE的产品，你不要去学习什么排序，除非你想考古。
一、排序（物理排序）
通常记录是按输入的顺序（物理顺序）存放在数据表中的，排序是指表的所有记录按指定字段的值的大小顺序进行重新排列到新的数据表文件中。
二、索引（逻辑排序）
与排序相比，索引是一种逻辑排序方法，它不改变记录在物理上的排列顺序，而是建立一个与原文件相对应的索引文件，索引文件中存储了一组记录指针，它指向原文件的记录。

荷兰提出的单元危险快速排序法有何优点

1.设排序总量为n,快排的时间为nlogn.

2.随机的数列、基本无序的序列，不适合基本有序的序列。

3.快排是比较排序中速度最快的排序，这是快排的优点。缺点是快排是不稳定，排序效率和初始序列的状态有关，对基本有序的序列，效率很差。

4.时间复杂度：O（nlogn），空间复杂度：O(nlogn)(此处计算了堆栈的占用);

5.快排是不稳定的排序。

6.比较（交换）排序法，是用过比较和交换排序的，这是由快排的算法实现决定的。

有什么不明白的，可以消息我，不要hi我，我乐意为您解答。

排序法的排序法的分类

排序法可分为简单排序法和交替排序法。
1、简单排序法
简单排序法也称序列评定法，是指管理者把本部门的所有员工从绩效最高者到绩效最低者(或从最好者到最差者)进行排序，即对一批考核对象按照一定标准排出“1、2、3、4……”的顺序。
该方法也应用也工作评价上，由负责工作评价的人员，根据其对企业各项工作的经验认识和主观判断，对各项工作在企业中的相对价值进行整体的比较，并加以排队。在对各项工作进行比较排序时，一般要求工作评价人员综合考虑以下各项因素:工作职责、工作权限、岗位资格、工作条件、工作环境等。权衡各项工作在各项因素上的轻重程度并排定秩序后，将其划入不同的工资等级内。
简单排序法的优缺点
优点
该方法的优点是简便易行，具有一定的可信性，可以完全避免趋中倾向或宽严误差。
缺点
缺点是考核的人数不能过多，以5—15人为宜，而且只适用于考核同类职务的人员，应用范围受限，不适合在跨部门人事调整方面应用。
2、交替排序法
交替排序法则是指管理者对被评估员工的名单进行审查后，从中找出工作绩效最好的员工列为第一名，并将其的名字从名单上划去。然后从剩下的名单中找出工作绩效最差的员工排为最后一名，也把其名字从名单中划去。随后，在剩下的员工中管理者再找出一名工作绩效最好的员工将其排为第二名，找出一名最差的员工列为倒数第二名，以此类推，直到将所有的员工排序完。