# 如何对很多重复的大数组进行排序？

## 本文概述

``````Example:
Input:  arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1}
Output: arr[] = {1, 1, 1, 1, 1, 12, 12, 12, 100, 100, 100, 100}``````

``````struct Node
{
int key;
struct Node *left. *right;
int count;  //Added to handle duplicates

//Other tree node info for balancing like height in AVL
}``````

1)创建一个空的AVL树, 并将count作为附加字段。

2)遍历输入数组, 并对每个元素” arr [i]”执行以下操作

…..a)如果树中不存在arr [i], 则将其插入并将count初始化为1

…..b)否则在树中增加其计数。

3)进行树的有序遍历。在执行顺序操作时, 将每个键的计数时间放入arr []中。

2nd步骤需要O(n Log m)时间和3rd步骤需要O(n)时间。因此, 总体时间复杂度为O(n Log m)

## C ++

``````//C++ program to sort an array using AVL tree
#include<iostream>
using namespace std;

//An AVL tree Node
struct Node
{
int key;
struct Node *left, *right;
int height, count;
};

//Function to insert a key in AVL Tree, if key is already present, //then it increments count in key's node.
struct Node* insert( struct Node* Node, int key);

//This function puts inorder traversal of AVL Tree in arr[]
void inorder( int arr[], struct Node *root, int *index_ptr);

//An AVL tree based sorting function for sorting an array with
//duplicates
void sort( int arr[], int n)
{
//Create an empty AVL Tree
struct Node *root = NULL;

//Insert all nodes one by one in AVL tree. The insert function
//increments count if key is already present
for ( int i=0; i<n; i++)
root = insert(root, arr[i]);

//Do inorder traversal to put elements back in sorted order
int index = 0;
inorder(arr, root, &index);
}

//This function puts inorder traversal of AVL Tree in arr[]
void inorder( int arr[], struct Node *root, int *index_ptr)
{
if (root != NULL)
{
//Recur for left child
inorder(arr, root->left, index_ptr);

//Put all occurrences of root's key in arr[]
for ( int i=0; i<root->count; i++)
{
arr[*index_ptr] = root->key;
(*index_ptr)++;
}

//Recur for right child
inorder(arr, root->right, index_ptr);
}
}

//A utility function to get height of the tree
int height( struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

//Helper function that allocates a new Node
struct Node* newNode( int key)
{
struct Node* node = new Node;
node->key   = key;
node->left   = node->right = NULL;
node->height = node->count = 1;
return (node);
}

//A utility function to right rotate subtree rooted
//with y.
struct Node *rightRotate( struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;

//Perform rotation
x->right = y;
y->left = T2;

//Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;

//Return new root
return x;
}

//A utility function to left rotate subtree rooted with x
struct Node *leftRotate( struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;

//Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;

//Return new root
return y;
}

//Get Balance factor of Node N
int getBalance( struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

//Function to insert a key in AVL Tree, if key is already
//present, then it increments count in key's node.
struct Node* insert( struct Node* Node, int key)
{
/* 1.  Perform the normal BST rotation */
if (Node == NULL)
return (newNode(key));

//If key already exists in BST, icnrement count and return
if (key == Node->key)
{
(Node->count)++;
return Node;
}

/* Otherwise, recur down the tree */
if (key <Node->key)
Node->left  = insert(Node->left, key);
else
Node->right = insert(Node->right, key);

/* 2. Update height of this ancestor Node */
Node->height = max(height(Node->left), height(Node->right)) + 1;

/* 3. Get the balance factor of this ancestor Node to
check whether this Node became unbalanced */
int balance = getBalance(Node);

//If this Node becomes unbalanced, then there are 4 cases

//Left Left Case
if (balance> 1 && key <Node->left->key)
return rightRotate(Node);

//Right Right Case
if (balance <-1 && key> Node->right->key)
return leftRotate(Node);

//Left Right Case
if (balance> 1 && key> Node->left->key)
{
Node->left =  leftRotate(Node->left);
return rightRotate(Node);
}

//Right Left Case
if (balance <-1 && key <Node->right->key)
{
Node->right = rightRotate(Node->right);
return leftRotate(Node);
}

/* return the (unchanged) Node pointer */
return Node;
}

//A utility function to print an array
void printArr( int arr[], int n)
{
for ( int i=0; i<n; i++)
cout <<arr[i] <<", " ;
cout <<endl;
}

/* Driver program to test above function*/
int main()
{
int arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1};
int n = sizeof (arr)/sizeof (arr[0]);

cout <<"Input array is\n" ;
printArr(arr, n);

sort(arr, n);

cout <<"Sorted array is\n" ;
printArr(arr, n);
}``````

## Java

``````//Java program for insertion in AVL Tree
public class AvlTree
{

static Node root = null ;

static class Node
{
int key, height, count;
Node left, right;

Node( int d)
{
key = d;
height = 1 ;
count = 1 ;
left = right = null ;
}
}

//A utility function to get the height of the tree
int height(Node N)
{
if (N == null )
return 0 ;

return N.height;
}

//A utility function to get maximum of two integers
int max( int a, int b)
{
return (a> b) ? a : b;
}

//A utility function to right rotate subtree rooted with y
//See the diagram given above.
Node rightRotate(Node y)
{
Node x = y.left;
Node T2 = x.right;

//Perform rotation
x.right = y;
y.left = T2;

//Update heights
y.height = max(height(y.left), height(y.right)) + 1 ;
x.height = max(height(x.left), height(x.right)) + 1 ;

//Return new root
return x;
}

//A utility function to left rotate subtree rooted with x
//See the diagram given above.
Node leftRotate(Node x)
{
Node y = x.right;
Node T2 = y.left;

//Perform rotation
y.left = x;
x.right = T2;

//Update heights
x.height = max(height(x.left), height(x.right)) + 1 ;
y.height = max(height(y.left), height(y.right)) + 1 ;

//Return new root
return y;
}

//Get Balance factor of node N
int getBalance(Node N)
{
if (N == null )
return 0 ;

return height(N.left) - height(N.right);
}

Node insert(Node node, int key)
{

/* 1. Perform the normal BST insertion */
if (node == null )
return ( new Node(key));

if (key <node.key)
node.left = insert(node.left, key);
else if (key> node.key)
node.right = insert(node.right, key);

//Duplicate keys not allowed
else
{
node.count++;
return node;
}

/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left), height(node.right));

/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);

//If this node becomes unbalanced, then there
//are 4 cases Left Left Case
if (balance> 1 && key <node.left.key)
return rightRotate(node);

//Right Right Case
if (balance <- 1 && key> node.right.key)
return leftRotate(node);

//Left Right Case
if (balance> 1 && key> node.left.key)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}

//Right Left Case
if (balance <- 1 && key <node.right.key)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}

/* return the (unchanged) node pointer */
return node;
}

//inorder traversal in BST always give sorted
//order. Put the sorted elements back into the array
int inorder(Node n, int arr[], int i)
{
if (n != null )
{
i = inorder(n.left, arr, i);
for ( int j = 0 ; j <n.count; j++)
{
arr[i] = n.key;
i++;
}
i = inorder(n.right, arr, i);
}
return i;
}

//Driver code
public static void main(String[] args)
{
//TODO Auto-generated method stub
int arr[] = { 100 , 12 , 100 , 1 , 1 , 12 , 100 , 1 , 12 , 100 , 1 , 1 };
System.out.println( "Input array " );
for ( int i = 0 ; i <arr.length; i++)
System.out.print( " " + arr[i]);

AvlTree at= new AvlTree();

//insert all element in AVL tree
for ( int i = 0 ; i <arr.length; i++)
root = at.insert(root, arr[i]);

//Do inorder traversal to put
//elements back in sorted order
int index = 0 ;
at.inorder(root, arr, index);
System.out.println( "\nOutput array " );
for ( int i = 0 ; i <arr.length; i++)
System.out.print( " " + arr[i]);
}
}

//This code is contributed by moonishussain``````

``````Input array is
100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1, Sorted array is
1, 1, 1, 1, 1, 12, 12, 12, 100, 100, 100, 100,``````

1)创建一个空的哈希表。输入数组值存储为键, 其计数存储为哈希表中的值。

2)对于arr []的每个元素” x”, 请执行以下操作

…..a)如果哈希表中存在x ix, 则增加其值

…..b)否则插入x等于1的值。

3)考虑哈希表的所有键并对它们进行排序。

4)遍历所有排序的键并打印每个键的值倍。

``````//A C++ program to sort a big array with many repetitions

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

void sort( int arr[], int n)
{
//1. Create an empty hash table.
map<int , int> count;

//2. Input array values are stores as key and their
//counts are stored as value in hash table.
for ( int i=0; i<n; i++)
count[arr[i]]++;

map<int , int>::iterator it;
int index = 0;

//3. Consider all keys of hash table and sort them.
//In std::map, keys are already sorted.

//4. Traverse all sorted keys and print every key its value times.
for (it=count.begin(); it!=count.end(); ++it)
{
while (it->second--)
arr[index++]=it->first;
}
}

//Utility function to print an array
void printArray( int arr[], int n)
{
for ( int i=0; i<n; i++)
cout <<arr[i] <<" " ;
cout <<endl;
}

//Driver program to test above function.
int main()
{
int arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1};
int n = sizeof (arr)/sizeof (arr[0]);

cout <<"Input array is\n" ;
printArray(arr, n);

sort(arr, n);

cout <<"Sorted array is\n" ;
printArray(arr, n);

return 0;
}
//Contributed by Aditya Goel``````

``````Input array is
100 12 100 1 1 12 100 1 12 100 1 1
Sorted array is
1 1 1 1 1 12 12 12 100 100 100 100``````

• 回顶