统计汉字出现次数并排序

使用了三种常用的排序方法：冒泡排序，选择排序和快速排序

1.冒泡排序法（时间复杂度O(n2))

原理：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

maopao_sort

2.选择排序法(时间复杂度为O（nlog2n）)

算法描述：选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换。

xuanze_sort

3.快速排序法

quick_sort
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
另外，汉字与字母不同，每个汉字需要两个字节来存放，所以需要两个char类型变量；此题还可以使用结构体来实现。

C语言实例:

输入输出结果：

sort_result

代码实现：

#include<iostream>
#include<string.h>
using namespace std;

//1.冒泡排序法。
void sort1(char* x, int size)
{
  int count[50] = {};//计数数组count
  char index[50][2] = {};//临时数组index
  int i, j, k = 0, ti;
  char tc1,tc2;//交换时的中间变量,其中汉字需要两字节存放
  for (i = 0; i < size; i+=2)
  {
    for (j = i - 2; j >= 0; j-=2)
    {
      if (x[i] == x[j]&amp;&amp;x[i+1]==x[j+1])
        break;
    }
    if (j == -2)
    {
      index[k][0] = x[i];//统计有多少不重复的字符
      index[k][1] = x[i + 1];
      k++;
    }
  }
  for (i = 0; i < k; i++)
  {
    for (j = 0; j < size; j+=2)
    {
      if (index[i][0] == x[j]&amp;&amp;index[i][1]==x[j+1])
        count[i]++;//记录每个字符出现次数
    }
  }
  for (i = 1; i < k; i++)//记趟数
  {
    for (j = 0; j < k - i; j++)
    {
      if (count[j] > count[j + 1])
      {
        ti = count[j], count[j] = count[j + 1], count[j + 1] = ti;
        tc1 = index[j][0], index[j][0] = index[j + 1][0], index[j + 1][0] = tc1;
        tc2 = index[j][1], index[j][1] = index[j + 1][1], index[j + 1][1] = tc2;
      }
    }
  }
  for (i = 0; i < k; i++)
    printf("%c%c:%d ", index[i][0],index[i][1], count[i]);
}


//2.选择排序法。
void sort2(char* x, int size)
{
  int count[50] = {};//计数数组count
  char index[50][2] = {};//临时数组index
  int i, j, k = 0, ti;
  char tc1, tc2;//交换时的中间变量tc1.tc2,其中汉字需要两字节存放
  for (i = 0; i < size; i += 2)
  {
    for (j = i - 2; j >= 0; j -= 2)
    {
      if (x[i] == x[j] &amp;&amp; x[i + 1] == x[j + 1])
        break;
    }
    if (j == -2)
    {
      index[k][0] = x[i];//统计有多少不重复的字符
      index[k][1] = x[i + 1];
      k++;
    }
  }
  for (i = 0; i < k; i++)
  {
    for (j = 0; j < size; j += 2)
    {
      if (index[i][0] == x[j] &amp;&amp; index[i][1] == x[j + 1])
        count[i]++;//记录每个字符出现次数
    }
  }
  for (i = 1; i < k; i++)//记趟数
  {
    int max = 0;//首先查找最大值并存放在max中
    for (j = 1; j < k - i; j++)
      if (count[max] < count[j])
        max = j;
    ti = count[max], count[max] = count[k - i], count[k - i] = ti;
    tc1 = index[max][0], index[max][0] = index[k - i][0], index[k - i][0] = tc1;
    tc2 = index[max][1], index[max][1] = index[k - i][1], index[k - i][1] = tc2;
  }
  for (i = 0; i < k; i++)
    printf("%c%c:%d ", index[i][0], index[i][1], count[i]);
}




//3.1快速排序法递归部分
void sort(char index[][2], int count[], int low, int high)
{
  int i = low, j = high+1;
  int key = count[low];
  if (high <= low)
    return;
  while (true)
  {
    while (count[++i] < key)//从左往右找比key小的值
    {
      if (i == high)
        break;
    }
    while (count[--j] > key)//从右往左找比key大的值
    {
      if (j == low)
        break;
    }
    if (i >= j)
      break;
    char tc1, tc2;//交换时的中间变量tc1.tc2
    int ti;//int型变量中间值
    ti = count[j], count[j] = count[i], count[i] = ti;
    tc1 = index[j][0], index[j][0] = index[i][0], index[i][0] = tc1;
    tc2 = index[j][1], index[j][1] = index[i][1], index[i][1] = tc2;
  }
  //中间值交换
  int temp, tempc1, tempc2;
  temp = count[low], count[low] = count[j], count[j]=temp;
  tempc1 = index[low][0], index[low][0] = index[j][0], index[j][0] = tempc1;
  tempc2 = index[low][1], index[low][1] = index[j][1], index[j][1] = tempc2;
  sort(index, count, low, j - 1);
  sort(index, count, j + 1, high);
}

//3.快速排序法
void sort3(char* x, int size)
{
  int count[50] = {};//计数数组count
  char index[50][2] = {};//临时数组index
  int i, j, k = 0;//中间变量ti，计数变量i，j，k
  for(i = 0;i < size;i += 2)
  {
    for (j = i - 2; j >= 0; j -= 2)
    {
      if (x[i] == x[j] &amp;&amp; x[i + 1] == x[j + 1])
        break;
    }
    if (j == -2)
    {
      index[k][0] = x[i];//统计有多少不重复的字符
      index[k][1] = x[i + 1];
      k++;
    }
  }
  for (i = 0; i < k; i++)
  {
    for (j = 0; j < size; j += 2)
    {
      if (index[i][0] == x[j] &amp;&amp; index[i][1] == x[j + 1])
        count[i]++;//记录每个字符出现次数
    }
  }
  sort(index, count, 0, k-1);
  for (i = 0; i < k; i++)
    printf("%c%c:%d ", index[i][0], index[i][1], count[i]);
}

int main()
{
  char s[100];
  gets_s(s);
  sort1(s, strlen(s));
  cout << endl;
  sort2(s, strlen(s));
  cout << endl;
  sort3(s, strlen(s));
  cout << endl;
}