最近在刷ACM经常用到排序，以前老是写冒泡，可把冒泡带到OJ里后发现经常超时，所以本想用快排，可是很多学长推荐用sort函数，因为自己写的快排写不好真的没有sort快，所以毅然决然选择sort函数

用法

1、sort函数可以三个参数也可以两个参数，必须的头文件#include < algorithm>和using namespace std;

2、它使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)


3、Sort函数有三个参数：（第三个参数可不写）


（1）第一个是要排序的数组的起始地址。


（2）第二个是结束的地址（最后一位要排序的地址）


（3）第三个参数是排序的方法，可以是从大到小也可是从小到大，还可以不写第三个参数，此时默认的排序方法是从小到大排序。

两个参数用法
#include <iostream>
#include <algorithm>
int main()
{
 int a[20]={2,4,1,23,5,76,0,43,24,65},i;
 for(i=0;i<20;i++)
  cout<<a[i]<<endl;
 sort(a,a+20);
 for(i=0;i<20;i++)
 cout<<a[i]<<endl;
 return 0;
}


输出结果是升序排列。（两个参数的sort默认升序排序）

三个参数
// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }//升序排列
bool myfunction2 (int i,int j) { return (i>j); }//降序排列

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
    int myints[8] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
    //std::sort (myints,myints+8,myfunction);不用vector的用法
    
  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)//输出
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

string 使用反向迭代器来完成逆序排列
#include <iostream>
using namespace std;
int main()
{
     string str("cvicses");
     string s(str.rbegin(),str.rend());
     cout << s <<endl;
     return 0;
}
//输出：sescivc

sort
sort参数
sort filename       #按照ASCII升序排序
sort -u filename    #排序并且去除重复
sort -r filename    #倒叙
sort -n filename    #数字排序
sort -n -k 2 -t : filename  #以：划分，按照第二列数字升序排序
参数：
-b   忽略每行前面开始出的空格字符。
-c   检查文件是否已经按照顺序排序。
-d   排序时，处理英文字母、数字及空格字符外，忽略其他的字符。
-f   排序时，将小写字母视为大写字母。
-i   排序时，除了040至176之间的ASCII字符外，忽略其他的字符。
-m   将几个排序好的文件进行合并。
-M   将前面3个字母依照月份的缩写进行排序。
-n   依照数值的大小排序。
-o<输出文件>   将排序后的结果存入指定的文件。
-r   以相反的顺序来排序。
-t<分隔字符>   指定排序时所用的栏位分隔字符。
+<起始栏位>-<结束栏位>   以指定的栏位来排序，范围由起始栏位到结束栏位的前一栏位。

实例
[root@server6 ~]# cat file
hahahha
apple
cat
pig
banana
dog
pig


去重

-
[root@server6 ~]# sort -u file
apple
banana
cat
dog
hahahha
pig


按照ASCII码升序排序

-
[root@server6 ~]# sort file
apple
banana
cat
dog
hahahha
pig
pig


反向排序

-
[root@server6 ~]# sort -r file
pig
pig
hahahha
dog
cat
banana
apple


-
[root@server6 ~]# cat file1 
2
4
2
1
11
76
34
23


数字排序（但并非我们想要的）

-
[root@server6 ~]# sort file1 

1
11
2
2
23
34
4
76


按照数字排序

-
[root@server6 ~]# sort -n file1

1
2
2
4
11
23
34
76


去重按照数字排序

-
[root@server6 ~]# sort -nu file1

1
2
4
11
23
34
76


去重按照数字倒序排序

-
[root@server6 ~]# sort -nur file1
76
34
23
11
4
2
1


-
[root@server6 ~]# cat file2
dog:80:5
cat:70:3
pig:90:4


按照数字排序

-
[root@server6 ~]# sort -n file2

cat:70:3
dog:80:5
pig:90:4


效果同上

-
[root@server6 ~]# sort -n -k 2 -t : file2

cat:70:3
dog:80:5
pig:90:4


以：划分列，进行排序

-
[root@server6 ~]# sort -n -k 3 -t : file2

cat:70:3
pig:90:4
dog:80:5


-
[root@server6 ~]# cat file2
Dog:80:5
cat:70:3
Pig:90:4


忽略大小写升序排序

-
[root@server6 ~]# sort -f file2

cat:70:3
Dog:80:5
Pig:90:4

 

Comparator是个接口，可重写compare()及equals()这两个方法,用于比价功能；如果是null的话，就是使用元素的默认顺序，如a,b,c,d,e,f,g，就是a,b,c,d,e,f,g这样，当然数字也是这样的。

 

compare（a,b）方法:根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

equals（obj）方法：仅当指定的对象也是一个 Comparator，并且强行实施与此 Comparator 相同的排序时才返回 true。

 

Collections.sort(list, new PriceComparator());的第二个参数返回一个int型的值，就相当于一个标志，告诉sort方法按什么顺序来对list进行排序。

具体实现代码方法如下：

Book实体类：

 

package com.tjcyjd.comparator;

import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.GregorianCalendar;
import java.util.Iterator;
import java.util.TreeMap;

/**
 * 书实体类
 * 
 * @author yjd
 * 
 */
public class Book implements Comparable { // 定义名为Book的类，默认继承自Object类
	public int id;// 编号
	public String name;// 名称
	public double price; // 价格
	private String author;// 作者
	public GregorianCalendar calendar;// 出版日期

	public Book() {
		this(0, "X", 0.0, new GregorianCalendar(), "");
	}

	public Book(int id, String name, double price, GregorianCalendar calender,
			String author) {
		this.id = id;
		this.name = name;
		this.price = price;
		this.calendar = calender;
		this.author = author;
	}

	// 重写继承自父类Object的方法，满足Book类信息描述的要求
	public String toString() {
		String showStr = id + "\t" + name; // 定义显示类信息的字符串
		DecimalFormat formatPrice = new DecimalFormat("0.00");// 格式化价格到小数点后两位
		showStr += "\t" + formatPrice.format(price);// 格式化价格
		showStr += "\t" + author;
		SimpleDateFormat formatDate = new SimpleDateFormat("yyyy年MM月dd日");
		showStr += "\t" + formatDate.format(calendar.getTime()); // 格式化时间
		return showStr; // 返回类信息字符串
	}

	public int compareTo(Object obj) {// Comparable接口中的方法
		Book b = (Book) obj;
		return this.id - b.id; // 按书的id比较大小，用于默认排序
	}

	public static void main(String[] args) {
		Book b1 = new Book(10000, "红楼梦", 150.86, new GregorianCalendar(2009,
				01, 25), "曹雪芹、高鄂");
		Book b2 = new Book(10001, "三国演义", 99.68, new GregorianCalendar(2008, 7,
				8), "罗贯中 ");
		Book b3 = new Book(10002, "水浒传", 100.8, new GregorianCalendar(2009, 6,
				28), "施耐庵 ");
		Book b4 = new Book(10003, "西游记", 120.8, new GregorianCalendar(2011, 6,
				8), "吴承恩");
		Book b5 = new Book(10004, "天龙八部", 10.4, new GregorianCalendar(2011, 9,
				23), "搜狐");
		TreeMap tm = new TreeMap();
		tm.put(b1, new Integer(255));
		tm.put(b2, new Integer(122));
		tm.put(b3, new Integer(688));
		tm.put(b4, new Integer(453));
		tm.put(b5, new Integer(40));
		Iterator it = tm.keySet().iterator();
		Object key = null, value = null;
		Book bb = null;
		while (it.hasNext()) {
			key = it.next();
			bb = (Book) key;
			value = tm.get(key);
			System.out.println(bb.toString() + "\t库存：" + tm.get(key));
		}
	}
}




自定义比较器和测试类：

 

 

package com.tjcyjd.comparator;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.GregorianCalendar;
import java.util.Iterator;
import java.util.List;

public class UseComparator {
	public static void main(String args[]) {
		List<Book> list = new ArrayList<Book>(); // 数组序列
		Book b1 = new Book(10000, "红楼梦", 150.86, new GregorianCalendar(2009,
				01, 25), "曹雪芹、高鄂");
		Book b2 = new Book(10001, "三国演义", 99.68, new GregorianCalendar(2008, 7,
				8), "罗贯中 ");
		Book b3 = new Book(10002, "水浒传", 100.8, new GregorianCalendar(2009, 6,
				28), "施耐庵 ");
		Book b4 = new Book(10003, "西游记", 120.8, new GregorianCalendar(2011, 6,
				8), "吴承恩");
		Book b5 = new Book(10004, "天龙八部", 10.4, new GregorianCalendar(2011, 9,
				23), "搜狐");
		list.add(b1);
		list.add(b2);
		list.add(b3);
		list.add(b4);
		list.add(b5);
		// Collections.sort(list); //没有默认比较器，不能排序
		System.out.println("数组序列中的元素:");
		myprint(list);
		Collections.sort(list, new PriceComparator()); // 根据价格排序
		System.out.println("按书的价格排序:");
		myprint(list);
		Collections.sort(list, new CalendarComparator()); // 根据时间排序
		System.out.println("按书的出版时间排序:");
		myprint(list);
	}

	// 自定义方法：分行打印输出list中的元素
	public static void myprint(List<Book> list) {
		Iterator it = list.iterator(); // 得到迭代器，用于遍历list中的所有元素
		while (it.hasNext()) {// 如果迭代器中有元素，则返回true
			System.out.println("\t" + it.next());// 显示该元素
		}
	}

	// 自定义比较器：按书的价格排序
	static class PriceComparator implements Comparator {
		public int compare(Object object1, Object object2) {// 实现接口中的方法
			Book p1 = (Book) object1; // 强制转换
			Book p2 = (Book) object2;
			return new Double(p1.price).compareTo(new Double(p2.price));
		}
	}

	// 自定义比较器：按书出版时间来排序
	static class CalendarComparator implements Comparator {
		public int compare(Object object1, Object object2) {// 实现接口中的方法
			Book p1 = (Book) object1; // 强制转换
			Book p2 = (Book) object2;
			return p2.calendar.compareTo(p1.calendar);
		}
	}
}




 

 

Java中Sort排序是非常常用的方法，这一章我们主要来认识一下Sort的用法和相关的实现。
一、数组Sort排序
升序排序，直接使用Arrays.Sort方法，例如：
int[] array = {10, 3, 6, 1, 4, 5, 9};
//正序排序
Arrays.sort(array);//会检查数组个数大于286且连续性好就使用归并排序，若小于47使用插入排序，其余情况使用双轴快速排序
System.out.println("升序排序：");
for (int num : array) {
        System.out.println(num);
}
降序排序，对于只输出数组的情况，可以倒叙循环访问，例如：
//倒序排序
//(1)由于不提供倒排方法，你可以倒叙输出
System.out.println("降序输出：");
for (int i = array.length - 1; i >= 0; i--) {
        System.out.println(array[i]);
}
降序排序，对于需要使用数组 的情况，可以创建一个新的数组，然后倒叙访问赋值，例如：
//(2)或者创建一个新的数组，倒叙保存到新数组
int[] descArray = new int[array.length];
for (int i = 0; i < array.length; i++) {
        descArray[i] = array[array.length - i - 1];
}
System.out.println("新数组降序输出：");
for (int num : descArray) {
        System.out.println(num);
}
降序排序，可以先将数组转为集合，然后使用Collections.reverse()反转集合，但是对于非引用类型，不可以使用Arrays.asList()，因为int[]会被当作一个类型，而不是数组。
所以可以使用Guava的Ints.asList()方法实现，该转换后的集合，实现了List接口的方法，直接将数组转入内部的数组变量，需要注意它并没有实现数组的操作方法，例如调用add会报错：
转换和排序例如：
//(3)或者使用Guava来实现
List<Integer> integersList = Ints.asList(array);
Collections.reverse(integersList);//冒泡交换
System.out.println("Guava降序输出：");
for (int num : integersList) {
    System.out.println(num);
}
转后的集合类是Guava中的IntArrayAsList，其类UML图如下：

二、集合Sort排序—包装类
本小节主要是对jdk类库中的包装类排序，例如：Integer、String等，这些类都已经重写了Compare方法，都有默认排序规则，例如对于Integer类型会比较其包装的值类型大小，对于String类型会以长度最小字符串为基准，逐一比较相同位置字符的ASCII码大小，如果都相同则比较字符串的长度。
以Integer为例子，升序排序：
//Integer集合，正序排序
List<Integer> list = new ArrayList<Integer>(Arrays.asList(10, 3, 6, 1, 4, 5, 9));
Collections.sort(list);
System.out.println("集合正序排序：");
for (Integer num : list) {
        System.out.println(num);
}
返回：
集合正序排序：
1
3
4
5
6
9
10
降序排序：
//倒叙排序
Comparator<Integer> reverseComparator = Collections.reverseOrder();
Collections.sort(list, reverseComparator);
System.out.println("集合倒叙排序：");
for (Integer num : list) {
    System.out.println(num);
}
返回：
集合倒叙排序：
10
9
6
5
4
3
1
三、集合Sort排序—自定义对象
除了两节所描述的情况，我们还会遇到对于自定义类排序的情况，例如我们现在有一个学生对象，想要根据年龄对其进行排序，学生类Student如下：
public class Student {

    private String name;

    private Integer age;

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    /**
     * 为了更好显示数据，我们重写toString()方法.
     * @return 显示变量的字符串
     */
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
（1） 第一种方式，是实现Comparable接口，重写接口方法。
该CompareTo()方法，如果指定的数与参数相等返回0；如果指定的数小于参数返回 -1；如果指定的数大于参数返回 1。
对于排序来讲，你可以认为当返回1时，指定的数和参数会进行交换，而非1时则不变，指定数可以当作原本的数组中靠前的数，而参数可以当作靠后的数，又因为只有靠前数大于靠后数时才返回1，所以大的会被放到后面，此时升序排序（方便记忆）。以此类推，倒序情况则相反。
升序排序，比Student类增加了Comparable接口，并实现升序排序：
public class StudentAsc implements Comparable<StudentAsc> {
    private String name;

    private Integer age;

    public StudentAsc(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    public int compareTo(StudentAsc o) {
        if(null == this.age) {
            return -1;
        }
        if(null == o.getAge()) {
            return 1;
        }
        return this.age.compareTo(o.getAge());
    }

    @Override
    public String toString() {
        return "StudentAsc{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

}
方法调用：
//正序排序，年龄为null时为小
StudentAsc studentWang = new StudentAsc("王小二", 10);
StudentAsc studentZhang = new StudentAsc("张三", 1);
StudentAsc studentGou = new StudentAsc("狗子", 99);
StudentAsc studentZhao = new StudentAsc("赵六", 40);
StudentAsc studentLi = new StudentAsc("李四", null);
List<StudentAsc> studentAscs = new ArrayList<StudentAsc>(Arrays.asList(studentWang, studentZhang, studentGou, studentZhao, studentLi));
Collections.sort(studentAscs);
System.out.println("自定义对象，升序排序：");
for(StudentAsc studentAsc : studentAscs) {
    System.out.println(studentAsc.toString());
}
返回：
自定义对象，升序排序：
Student{name='李四', age=null}
Student{name='张三', age=1}
Student{name='王小二', age=10}
Student{name='赵六', age=40}
Student{name='狗子', age=99}
降序排序，比Student类增加了Comparable接口，并实现倒序排序：
public class StudentDesc implements Comparable<StudentDesc> {
    private String name;

    private Integer age;

    public StudentDesc(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }

    public int compareTo(StudentDesc o) {
        if(null == this.age) {
            return 1;
        }
        if(null == o.getAge()) {
            return -1;
        }
        return o.age.compareTo(this.getAge());
    }

    @Override
    public String toString() {
        return "StudentDesc{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}
方法调用：
//降叙排序，年龄为null时为最大
StudentDesc studentWang = new StudentDesc("王小二", 10);
StudentDesc studentZhang = new StudentDesc("张三", 1);
StudentDesc studentGou = new StudentDesc("狗子", 99);
StudentDesc studentZhao = new StudentDesc("赵六", 40);
StudentDesc studentLi = new StudentDesc("李四", null);
List<StudentDesc> studentAscs = new ArrayList<StudentDesc>(Arrays.asList(studentWang, studentZhang, studentGou, studentZhao, studentLi));
Collections.sort(studentAscs);
System.out.println("自定义对象，降序排序：");
for(StudentDesc studentAsc : studentAscs) {
    System.out.println(studentAsc.toString());
}
返回：
自定义对象，降序排序：
Student{name='狗子', age=99}
Student{name='赵六', age=40}
Student{name='王小二', age=10}
Student{name='张三', age=1}
Student{name='李四', age=null}
（2）第二种方式，上面实现Comparable接口的方法并不十分灵活，比如对于一个类，在不同的地方需要使用不同的排序，此时再这样做就会显的十分繁琐。因此我们可以通过Collections.sort(List<T> list, Comparator<? super T> c)方法来实现，例子中，我们使用Student类，例子如下：
升序排序：
//升序排序
Student studentWang = new Student("王小二", 10);
Student studentZhang = new Student("张三", 1);
Student studentGou = new Student("狗子", 99);
Student studentZhao = new Student("赵六", 40);
Student studentLi = new Student("李四", null);
List<Student> students = new ArrayList<Student>(Arrays.asList(studentWang, studentZhang, studentGou, studentZhao, studentLi));
Collections.sort(students, new Comparator<Student>() {
    public int compare(Student o1, Student o2) {
        if(null == o1.getAge()) {
            return -1;
        }
        if(null == o2.getAge()) {
            return 1;
        }
        return o1.getAge().compareTo(o2.getAge());
    }
});
System.out.println("自定义对象，升序排序：");
for(Student student : students) {
    System.out.println(student.toString());
}
返回：
自定义对象，升序排序：
Student{name='李四', age=null}
Student{name='张三', age=1}
Student{name='王小二', age=10}
Student{name='赵六', age=40}
Student{name='狗子', age=99}
降序排序：
//降序排序
Student studentWang = new Student("王小二", 10);
Student studentZhang = new Student("张三", 1);
Student studentGou = new Student("狗子", 99);
Student studentZhao = new Student("赵六", 40);
Student studentLi = new Student("李四", null);
List<Student> students = new ArrayList<Student>(Arrays.asList(studentWang, studentZhang, studentGou, studentZhao, studentLi));
Collections.sort(students, new Comparator<Student>() {
    public int compare(Student o1, Student o2) {
        if(null == o1.getAge()) {
            return 1;
        }
        if(null == o2.getAge()) {
            return -1;
        }
        return o2.getAge().compareTo(o1.getAge());
    }
});
System.out.println("自定义对象，降序排序：");
for(Student student : students) {
    System.out.println(student.toString());
}
返回：
自定义对象，降序排序：
Student{name='狗子', age=99}
Student{name='赵六', age=40}
Student{name='王小二', age=10}
Student{name='张三', age=1}
Student{name='李四', age=null}

至此对数组、包装类集合、自定义集合排序做了总结，希望对大家有所帮助，如果有错误或问题可以留言在下方，敬请指正。