十大ソートアルゴリズムのc++実現【ヒルソート】【集計ソート】【速列】【バケツソート】【基数ソート】
5207 ワード
まず穴を切り,空になってから補充する
SortByBublle(int arr[], int n){
int temp = 0;
for (int i = 0; i < n; i++)
for(int j = i; j < n-1; j++){
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] =temp;
}
}
}SortBySelection(int arr[], int n){
int temp = 0, n = 0;
for (int i = 0; i < n; i++){
int min = arr[i];
for(int j = i; j < n; j++){ //
if (min < arr[j]){
min = arr[j];
n = j;
}
}
temp = arr[n]; //
arr[n] = arr[i];
arr[i] = temp;
}
}void SortByInsertion(int arr[], int len){
for (int i = 0; i < len - 1; i++)
for (int j = i+1; arr[j] < arr[j - 1] ; j--){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j -1] = temp;
}
}void SortByShell(int* arr, int len){
int gap = len / 2;
for (; gap > 0; gap = gap /2)
for (int i = 0; i + gap < len; i++){
if (arr[i] > arr[i + gap]){
int temp = arr[i];
arr[i] = arr[i +gap];
arr[i + gap] = temp;
}
}
}
/******************* **********************//******************* **********************/
int partition(int arr[], int start, int end) //
{
int i = start, j = end;
int temp = arr[i];
while (i < j)
{
while (i < j && arr[j] >= temp)
j--;
if (i < j)
{
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < temp)
i++;
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
arr[i] = temp;
return i;
}
void QuickSort(int arr[], int left, int right)
{
if (left > right)
return;
int m = partition(arr, left, right);
QuickSort(arr, left, m - 1);
QuickSort(arr, m + 1, right);
}
void SortByQuick(int arr[], int n)
{
QuickSort(arr, 0, n - 1);
}
/**************** *******************//**************** ************************/
int FindMax(int arr[], int len)
{
int maxnum = arr[0];
for (int i = 1; i < len; i++)
{
if (maxnum < arr[i])
maxnum = arr[i];
}
return maxnum;
}
void SortByCounting(int arr[], int len)
{
int n = FindMax(arr, len) + 1; //
std::vector coun(n);//** vector ； int* coun = new int[n];
for (int i = 0; i < len; i++)
{
coun[arr[i]]++;
}
for (int i = 0, j = 0; i < n; i++) //
{
while (coun[i]--)
{
arr[j] = i;
j++;
}
}
} /**************** ************************/
void SortBySelection(std::vector &arr, int len)
{
int temp = 0;
for (int j = 0; j < len; j++)
{
int min = arr[j];
int minI = j;
for (int i = j; i < len; i++)
{
if (min > arr[i])
{
minI = i;
min = arr[i];
}
}
temp = arr[j];
arr[j] = arr[minI];
arr[minI] = temp;
}
}
void SortByBucket(int arr[], int len)
{
int min = arr[0], max = arr[0];
for (int i = 0; i < len; i++)
{
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
int bucketNum = ceil((sqrt(float(len))));
int bucketSize = ceil((max - min) / float(bucketNum));
std::vector<:vector>> BK;// (bucketNum, std::vector());
BK.resize(bucketNum);
for (int i = 0; i < len; i++) //
{
int b = (arr[i] - min) / bucketSize;
BK[b].push_back(arr[i]);
}
int m = 0;
for (int j = 0; j < bucketNum; j++)
{
int s = BK[j].size();
SortBySelection(BK[j], s);//
for (int k = 0; k < s; k++)
{
arr[m] = BK[j][k]; //
m++;
}
}
} /**************** ************************/
void SortByRadix(int arr[], int len)
{
int maxNum = arr[0]; //
for (int i = 1; i < len; i++)
{
if (maxNum < arr[i])
maxNum = arr[i];
}
int k = 0;
while (maxNum) {
std::vector<:vector>> R;
R.resize(10);
for (int i = 0; i < len; i++)
{
int m = (arr[i] / (int(pow(10, k)))) % 10; //
R[m].push_back(arr[i]);
}
int x = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < R[i].size(); j++)
{
arr[x] = R[i][j];
x++;
//cout << R[i].size() << ' ';
}
}
maxNum = maxNum / 10;
k++; //
}
}