使用就地排序算法对对象进行排序

本文概述

C ++
Java
Python3
C#

给定一个数组红, 蓝色和黄色对象, 则任务是使用就地排序算法对数组进行排序, 以使所有蓝色对象出现在所有红色对象之前, 所有红色对象出现在所有黄色对象之前。
例子：

输入： arr[] = {“blue”, “red”, “yellow”, “blue”, “yellow”}
输出：blue blue red yellow yellow
输入：arr[] = {“red”, “blue”, “red”, “yellow”, “blue”}
输出：blue blue red red yellow

方法:首先，使用哈希表将蓝色、红色和黄色对象的值分别映射为1、2和3。现在，当需要比较两个对象时，请使用这些映射值。因此，该算法将对对象数组进行排序，使所有蓝色对象(映射到值1)首先出现，然后是所有红色对象(映射到值2)，然后是所有黄色对象(映射到值3)。
下面是上述方法的实现：
C ++

//C++ implementation of the approach #include < bits/stdc++.h> using namespace std; //Partition function which will partition //the array and into two parts int partition(vector< string> & objects, int l, int r, unordered_map< string, int> & hash) { int j = l - 1; int last_element = hash[objects[r]]; for ( int i = l; i < r; i++) {//Compare hash values of objects if (hash[objects[i]] < = last_element) { j++; swap(objects[i], objects[j]); } }j++; swap(objects[j], objects[r]); return j; }//Classic quicksort algorithm void quicksort(vector< string> & objects, int l, int r, unordered_map< string, int> & hash) { if (l < r) { int mid = partition(objects, l, r, hash); quicksort(objects, l, mid - 1, hash); quicksort(objects, mid + 1, r, hash); } }//Function to sort and print the objects void sortObj(vector< string> & objects) {//Create a hash table unordered_map< string, int> hash; //As the sorting order is blue objects, //red objects and then yellow objects hash[ "blue" ] = 1; hash[ "red" ] = 2; hash[ "yellow" ] = 3; //Quick sort function quicksort(objects, 0, int (objects.size() - 1), hash); //Printing the sorted array for ( int i = 0; i < objects.size(); i++) cout < < objects[i] < < " " ; }//Driver code int main() {//Let's represent objects as strings vector< string> objects{ "red" , "blue" , "red" , "yellow" , "blue" }; sortObj(objects); return 0; }

Java

//Java implementation of the approach import java.util.*; class GFG {//Partition function which will partition //the array and into two parts static int partition(Vector< String> objects, int l, int r, Map< String, Integer> hash) { int j = l - 1 ; int last_element = hash.get(objects.get(r)); for ( int i = l; i < r; i++) {//Compare hash values of objects if (hash.get(objects.get(i)) < = last_element) { j++; Collections.swap(objects, i, j); } }j++; Collections.swap(objects, j, r); return j; }//Classic quicksort algorithm static void quicksort(Vector< String> objects, int l, int r, Map< String, Integer> hash) { if (l < r) { int mid = partition(objects, l, r, hash); quicksort(objects, l, mid - 1 , hash); quicksort(objects, mid + 1 , r, hash); } }//Function to sort and print the objects static void sortObj(Vector< String> objects) {//Create a hash table Map< String, Integer> hash = new HashMap< > (); //As the sorting order is blue objects, //red objects and then yellow objects hash. put( "blue" , 1 ); hash. put( "red" , 2 ); hash. put( "yellow" , 3 ); //Quick sort function quicksort(objects, 0 , objects.size() - 1 , hash); //Printing the sorted array for ( int i = 0 ; i < objects.size(); i++) System.out.print(objects.get(i) + " " ); }//Driver code public static void main(String []args) { //Let's represent objects as strings Vector< String> objects = new Vector< > (Arrays.asList( "red" , "blue" , "red" , "yellow" , "blue" )); sortObj(objects); } }//This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach# Partition function which will partition # the array and into two parts objects = [] hash = dict ()def partition(l, r): global objects, hash j = l - 1last_element = hash [objects[r]]for i in range (l, r):# Compare hash values of objects if ( hash [objects[i]] < = last_element): j + = 1 (objects[i], objects[j]) = (objects[j], objects[i])j + = 1(objects[j], objects[r]) = (objects[r], objects[j])return j# Classic quicksort algorithm def quicksort(l, r): if (l < r): mid = partition(l, r) quicksort(l, mid - 1 ) quicksort(mid + 1 , r)# Function to sort and print the objects def sortObj(): global objects, hash# As the sorting order is blue objects, # red objects and then yellow objects hash [ "blue" ] = 1 hash [ "red" ] = 2 hash [ "yellow" ] = 3# Quick sort function quicksort( 0 , int ( len (objects) - 1 ))# Printing the sorted array for i in objects: print (i, end = " " )# Driver code# Let's represent objects as strings objects = [ "red" , "blue" , "red" , "yellow" , "blue" ]sortObj()# This code is contributed # by Mohit Kumar

//C# implementation of the approach using System; using System.Collections.Generic; class GFG {//Partition function which will partition //the array and into two parts static int partition(List< String> objects, int l, int r, Dictionary< String, int> hash) { int j = l - 1; String temp; int last_element = hash[objects[r]]; for ( int i = l; i < r; i++) {//Compare hash values of objects if (hash[objects[i]] < = last_element) { j++; temp = objects[i]; objects[i] = objects[j]; objects[j] = temp; } }j++; temp = objects[r]; objects[r] = objects[j]; objects[j] = temp; return j; }//Classic quicksort algorithm static void quicksort(List< String> objects, int l, int r, Dictionary< String, int> hash) { if (l < r) { int mid = partition(objects, l, r, hash); quicksort(objects, l, mid - 1, hash); quicksort(objects, mid + 1, r, hash); } }//Function to sort and print the objects static void sortObj(List< String> objects) {//Create a hash table Dictionary< String, int> hash = new Dictionary< String, int> (); //As the sorting order is blue objects, //red objects and then yellow objects hash.Add( "blue" , 1); hash.Add( "red" , 2); hash.Add( "yellow" , 3); //Quick sort function quicksort(objects, 0, objects.Count - 1, hash); //Printing the sorted array for ( int i = 0; i < objects.Count; i++) Console.Write(objects[i] + " " ); }//Driver code public static void Main(String []args) { //Let's represent objects as strings List< String> objects = new List< String> { "red" , "blue" , "red" , "yellow" , "blue" }; sortObj(objects); } }//This code is contributed by Rajput-Ji

【使用就地排序算法对对象进行排序】输出如下：