ElasticSearch之排序使用-ES常用排序方法
 
  
       在搜索系统中，最常遇到的一个需求就是排序，同时排序也是搜索引擎需要改造最多的地方。
 
 
 
常见排序一般有如下两类：
 （1）按照相似度匹配得分排序
 
（2）按照指定字段排序
 
    相似度得分排序是系统默认的排序方式，更多时候，我们需要按照指定字段排序。lucene中，基于字段内容的排序是由FieldComparator接口来实现的，在排序中又分为单字段排序和多字段排序。在排序速度方面，数值类型排序速度最快，在lucene中数值类型的排序是由 NumericComparator 的派生类来实现，NumericComparator派生类支持 float、double、int 、long 四钟类型（日期在底层会转化为long型存储）。
      字符串类型的字段一般都需要进行搜索的，那么需要对其进行分词处理。分词处理的结果就是将该字符串解析为多个词条。在lucene层面，根据docid可以取到多个索引词条，而无论采用哪个索引词条来进行排序其实都正确。
      所以为了对字符串类型字段进行排序，需要保存整个字符串作为一个索引词条，同时为了保证该字段能够被搜索，还要保存该字符串analyzed的结果（即需要保存完整的字符串作为一个词条，同时又分词索引）。

 在ES中为实现该功能，ES提供了 multi-field mapping 机制，配置通过配置即可实现字段即分词，又可排序：

 "title": {  
     "type":     "string",
     "analyzer": "ansj",
     "fields": {
         "sort": {
             "type":  "string",
             "index": "not_analyzed"
         }
     }
 }

 通过title字段作为搜索，而用title.sort字段作为排序：

 GET /_search
 {
     "query": {
         "match": {
             "title": "elasticsearch"
         }
     },
     "sort": "title.sort"
 
}
 
 
 
Lucene标准语法中多字段排序：
 {
   "from": 0,
   "size": 10,
   "query": {
     "query_string": {    "query": "*:*",    "default_operator": "and"  }
   },
   "sort": [
 
    {   
 
     "title.sort": { "order": "desc"   },
 
      "_score": {   "order": "desc"   }
     }
   ]
 
}
 
缺省字段排序：
 
{
   "from": 0,
   "size": 10,
   "query": {
     "query_string": {    "query": "title:test",    "default_operator": "and"   }
   },
   "sort": [
     {
       "rpgendatetime": {      "order": "desc",      "missing": "_last"     }
     }
   ]
 }
 
使用脚本排序：
 
 
 
{
    "query" : {
     "query_string": {
         "query": "",
         "default_operator": "and"
          }
    },
    "sort" : {
        "_script" : {
            "type" : "number",
            "script" : {
                "inline": "doc['field_name'].value * factor",
                "params" : {
                    "factor" : 1.1
                }
            },
            "order" : "asc"
        }
    }
}

声明：此文章仅供学习排序方法的原理，不附加代码
 
 
 
一。常用排序方法
 
1. 冒泡排序（Bubble Sort）
 2. 直接选择排序（Straight Selection Sort）
 3. 直接插入排序（Straight Insertion Sort）
 4. 希尔排序（Shells Sort）
 5. 堆排序（Heap Sort）
 6. 快速排序（Quick Sort）
 7. 归并排序（Merge Sort）
 8. 桶排序（Bucket Sort）/基数排序（Radix Sort）
 
二。简介实现方法（皆以从小到大排列为例，设在正整数的情况下，如有其他情况请对比考虑）   注：附图皆为百度所得，感谢图主分享。
 
1.冒泡排序，冒泡排序作为初学程序的第一种排序方法，其方法是对序列中所有数实行前后元素对比，小的在前大的在后，这样从头到尾进行n-1次
 
2.直接选择排序，又叫简单选择排序，其方法是将序列中最小的元素比较出来放到序列头部，然后剩下的元素按此方法继续比较选择。白话说，就是直接选择出最小的挨个放
 
3.直接插入排序，其方法是将序列11111111（1代表元素，不代表数值）看作两部分暂且用a来隔离这两部分，即1a1111111，a前为已经排好位置的元素，a后为未排好位置的元素，然后依次取出a后的元素与a前比较，放在合适的位置，即初始1a111111，第一次排序完之后为11a11111。白话说，就是挨个来找位置插入
 
4.希尔排序，又叫做缩小增量排序，是直接插入排序的基础上进行的改进。方法是取间隔a的数进行比较，这个a称为增量，若前数大于后数，则将其交换位置，从头到尾全部比较完成后，再按照间隔a/2进行比较，若a是奇数，则按照 (a+1)/2的间隔计算，直至当增量a=1时，比较完a=1这一趟，便结束排序。附图为比较过程：
 
                   
 
5.快速排序，在冒泡法的基础上进行的改进，序列arr，标记头尾为i ，j，设标记量temp = arr[i] 也就是arr[0]
 
j开始 --，直到有arr[j]<temp，此时j找到位置了，站在此处不动，i开始动
 
i开始++，直到有arr[i]>temp，此时i找到位置了，站在此处不动，j再开始动
 
直到j与i相遇了，哎此时相遇位置的数与temp进行交换
 
第一次排序结束，相遇位置左侧元素便均小于temp，右方均大于temp
 
利用这种方法对两侧进行递归操作，直到temp实在无法拆分左右停止，次数的序列便排序完成。
 
附图第一次排序心路历程。
 
               temp在此，谁敢放肆！                 
 
        
 
     
 
           
 
         
 
             
 
 
 
6.归并排序，采用”分治策略“，灵感来自归并操作。首先理解什么是归并操作？？
 
归并操作是指两个有序列表，合成一个有序表。
 
设俩表为：    abcdefg     ABCDEFG
 
取两个列表得第一个元素比较，谁小谁放在合并表首位，后续元素依次前进，即第一次归并得 ：（设a<A）
 
bcdefg   ABCDEFG,       合并表为 a
 
继续重复此操作，若有一方为空了，则将另一方元素直接跟随在合并表表尾  （设此时剩下efg）
 
此时： efg      null            合并表为   abABCDEcdFG，故： abABCDEcdFG +efg  = abABCDEcdFGefg 
 
好，理解了归并操作，来讲解什么是归并排序。
 
分治，也可以叫分合
 
（1）分，将序列分解
 
                
 
（2）治，合，将分解后得小模块进行归并操作
 
                例如：8  4 进行归并操作得到合并序列  4 8
 
                            4 8           5 7序列进行归并操作得到合并序列4 5 7 8
 
               
 
注：https://www.cnblogs.com/crystalmoore/p/5930841.html  这位博主有个动态演示，可以进去看一下
 
7.堆排序，堆排序是基于堆的概念上设计的排序算法
 
   堆，一般常用的也就是二叉堆，二叉堆的可以形象的比喻成一颗 完全二叉树。（对于堆与二叉树在此不多解释，需要的同学们请自行百度学习）。而二叉堆中分为大顶堆和小顶堆。
 
   大顶堆是节点处的值大于等于左右孩子，小顶堆是节点处的值小于等于左右孩子。附图：   左大右小
 
     
 
    一般升序采用大顶堆，降序采用小顶堆
 
    将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
 
    说白了，先将序列看作是一个完全二叉树，从最后一个非叶子节点开始，
 
    （1）将结点及其叶子，进行比较，把最大的换到结点处，这样一层层的把最大的节点拱到了堆顶
 
    （2）将堆顶元素跟末尾元素进行交换，这样就将最大值放到了序列最后
 
    （3）此时将剩余数看作完全二叉树进行如此计算，一步一步的将最大值拱出来，剩下一个节点无左右孩子的时候，排序完成。
 
   参考：https://www.cnblogs.com/chengxiao/p/6129630.html
 
8.桶排序，又称桶排序
 
其方法主要是：
 
（1）从序列中找出最大值N，设置一个数组arr，并使其所有值为0，长度为N+1，其数组下标0--N也就代表了这N+1个桶
 
（2）将所有数据放入他所匹配的下标桶，并在放入时使得此处arr得值加1表示计数
 
（3）根据桶的下标取出所存在的元素，若某个桶得值为0，则直接跳过，通过桶得下标排序，通过桶的值判断有多少元素在这个桶里存放
 
（4）排序结束，出现结果
 
三。所有常用排序之间得比较（图来自百度，感谢图主无私分享）
 
      

大家好，我是IT修真院郑州分院第八期的学员，今天给大家分享一下，题目常见的排序方法有哪些。
 

一、背景介绍
 
排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。
 
查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。
 
 
 
二、知识剖析
 
常见的排序算法：冒泡排序、快速排序和归并排序。
 
 
 
冒泡排序
 
算法原理：冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换时，此时该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 
具体算法描述：
 
1.   比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 
2.   对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 
3.   针对所有的元素重复以上的步骤，除了最后一个；
 
4.   重复步骤 1 31 3，直到排序完成。
 
 
 
快速排序
 
算法原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 
具体算法描述：
 
1.   从数列中挑出一个元素，称为 “基准”（pivot）；
 
2.   重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 
3.   递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 
 
 
归并排序
 
算法原理：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 
具体算法描述：
 
1.   把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
 
2.   对这两个子序列分别采用归并排序；
 
3.   将两个排序好的子序列合并成一个最终的排序序列。
 

三、常见问题
 
如何在js中实现上述算法？
 

四、 解决方案
 
视频
 
五、编码实战
 
 PPT
 

六、拓展思考
 
原生js中有自带的排序的函数sort()，angularjs中排序的方法是自带的过滤器orderby
 
 
 
七、参考文献
 
参考：js排序算法汇总
 
 
 

八、更多讨论
 
讨论一：各排序方法的的时间复杂度比较？
 
排序算法
平均时间复杂度
最好情况
最坏情况
空间复杂度
排序方式
稳定性
冒泡排序
O(n2)O(n2)
O(n)O(n)
O(n2)O(n2)
O(1)O(1)
内排序
稳定
选择排序
O(n2)O(n2)
O(n2)O(n2)
O(n2)O(n2)
O(1)O(1)
内排序
不稳定
插入排序
O(n2)O(n2)
O(n)O(n)
O(n2)O(n2)
O(1)O(1)
内排序
稳定
希尔排序
O(nlogn)O(nlog⁡n)
O(n(log22n))O(n(log22⁡n))
O(n(log22n))O(n(log22⁡n))
O(1)O(1)
内排序
不稳定
归并排序
O(nlogn)O(nlog⁡n)
O(nlogn)O(nlog⁡n)
O(nlogn)O(nlog⁡n)
O(n)O(n)
外排序
稳定
快速排序
O(nlogn)O(nlog⁡n)
O(nlogn)O(nlog⁡n)
O(n2)O(n2)
O(logn)O(log⁡n)
内排序
不稳定
堆排序
O(nlogn)O(nlog⁡n)
O(nlogn)O(nlog⁡n)
O(nlogn)O(nlog⁡n)
O(1)O(1)
内排序
不稳定
计数排序
O(n+k)O(n+k)
O(n+k)O(n+k)
O(n+k)O(n+k)
O(k)O(k)
外排序
稳定
桶排序
O(n+k)O(n+k)
O(n+k)O(n+k)
O(n2)O(n2)
O(n+k)O(n+k)
外排序
稳定
基数排序
O(n×k)O(n×k)
O(n×k)O(n×k)
O(n×k)O(n×k)
O(n+k)O(n+k)
外排序
稳定
数据量小的时候快速排序最快，归并排序其次，冒泡排序最次；数据大的情况的下归并排序的性能超过快速排序。归并排序的稳定性是三者之中最好的。讨论二：三个排序哪个效率最高?
 
讨论三：怎么判断一个排序算法的好坏？
 
首先要保证其正确性，在正确性的基础上比较其代码可读性，时间复杂度，空间复杂度，稳定性。
 
感谢大家观看！
 
今天的分享就到这里啦，欢迎大家点赞、转发、留言、拍砖~

C语言三种常用的排序方法：冒泡排序，插入排序，快速排序
 
冒泡排序：
 
 
void maopao(int a[])
{
	int temp;
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
}
插入排序： 
 
 
void insert(int a[])
{
	int temp;
	int j;
	for (int i = 1; i < n; i++)
	{
		j = i;
		temp = a[i];
		while (temp < a[j - 1] && j >= 1)
		{
			a[j] = a[j - 1];
			j--;
		}
		a[j] = temp;

	}
}
快速排序： 
 
 
void Quick_sort(int low,int high,int a[])
{
	if (low >= high)
		return;
	int first = low;
	int last = high;
	int key = a[first];

	while (first < last)
	{
		while (first < last&&a[last]>=key)
		{
			last--;
		}
		a[first] = a[last];
		while (first<last&&a[first]<= key)
			first++;
		a[last] = a[first];
	}
	a[first] = key;
	Quick_sort(low, first - 1, a);
	Quick_sort(first+1, high, a);
}


 
堆排序：
 
//堆调整，构建大顶堆
 
 
void adjust(int a[], int i, int n)
{
	int child, tmp;

	for (; 2 * i + 1 < n; i = child)
	{
		child = 2 * i + 1;
		if (child<n - 1 && a[child] < a[child + 1])
			child++;
		if (a[i] < a[child])
		{
			tmp = a[child];
			a[child] = a[i];
			a[i] = tmp;
		}
		else
			break;
	}
}
void heap(int a[], int n)
{
	int temp;
	//将数组进行大顶堆的构建
	for (int i = n / 2 - 1; i >= 0; i--)
		adjust(a, i, n);
	//将堆顶元素放到数组的最后一位，然后逐渐缩小数组
	for (int i = n-1; i >0; i--)
	{
		temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		adjust(a, 0, i);

	}

}

 
希尔排序：
 
是在插入排序的基础上采用希尔增量，初始增量为N/2，然后每次增量为上一次的二分之一
 

void shell(int a[], int n)
{
	int increase,tmp;
	for (increase = n / 2; increase >= 1; increase /= 2)
		for (int i = increase; i < n; i++)
		{
			int j;
			tmp = a[i];
			for ( j = i; j >=0&&a[j-increase]>tmp; j -= increase)
			{
				a[j] = a[j - increase];
			}
			a[j] = tmp;
		}
}