정렬(2) - 삽입/힐/선택/빠른 정렬 및 최적화
<strong><span style="font-size:18px;">#pragma once
#include <iostream>
using namespace std;
#include <assert.h>
#include <stack>
void InsertSort(int* arr,size_t size)//
{
assert(arr);
for (int i = 1;i < size;i++)
{
int j = i-1;
int tmp = arr[i];
while (arr[j] > tmp && j >= 0)
{
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = tmp;
}
}
void SellSort(int* arr,size_t size)//
{
assert(arr);
int k = size;
while (k > 1)
{
k = k / 3 + 1;
for (int i = k; i < size;i ++)
{
int tmp = arr[i];
int j = i - k;
while (arr[j] > tmp && j >= 0)
{
arr[j + k] = arr[j];
j -= k;
}
arr[j + k] = tmp;
}
}
}
void SelectSort(int* arr,size_t size)//
{
assert(arr);
for (int i = 0;i < size;i++)
{
int min = i;
for (int j = i+1;j < size;j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
//arr[i] = arr[min];// , , , ,
swap(arr[i],arr[min]);
}
}
void SelectSort_OP(int* arr,size_t size)//
{
assert(arr);
int left = 0;
int right = size - 1;
while (left < right)
{
int MinIndex = left;
int MaxIndex = right;
for (int i = left;i <= right;i++)
{
if (arr[i] < arr[MinIndex])
{
MinIndex = i;
}
if (arr[i] > arr[MaxIndex])
{
MaxIndex = i;
}
}
swap(arr[left],arr[MinIndex]);
if (MaxIndex == left)// 9 1 2 3 4 0
{
MaxIndex = MinIndex;
}
swap(arr[right],arr[MaxIndex]);
left++;
right--;
}
}
int PartSort(int* arr,int left,int right)//
{
assert(arr);
int k = arr[right];
int begin = left;
int end = right;
while (begin < end)
{
while (begin < end && arr[begin] <= k)//
{
begin++;
}
while (begin < end && arr[end] >= k)//
{
end--;
}
if (begin < end)
{
swap(arr[begin],arr[end]);
}
}
swap(arr[begin],arr[right]);
return begin;
}
void QuickSort(int* arr,int left,int right)// ( )
{
assert(arr);
if (left >= right)
{
return;
}
int div = PartSort(arr,left,right);
QuickSort(arr,left,div-1);
QuickSort(arr,div+1,right);
}
void QuickSort_NonR(int* arr,int left,int right)// ( )
{
assert(arr);
stack<int> _stack;
_stack.push(right);
_stack.push(left);
while (_stack.empty() == false)
{
int begin = _stack.top();
_stack.pop();
int end = _stack.top();
_stack.pop();
int div = PartSort(arr,begin,end);
if (begin < div-1)
{
_stack.push(div-1);
_stack.push(begin);
}
if (div+1 < end)
{
_stack.push(end);
_stack.push(div+1);
}
}
}</span></strong>
test.cpp
<strong><span style="font-size:18px;">#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"
void test1()//InsertSort
{
int arr[] = {1,4,3,8,2,9,8,4,6};
int size = sizeof(arr)/sizeof(arr[0]);
InsertSort(arr,size);
for (int i = 0;i < size;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void test2()//SellSort
{
int arr[] = {6,7,8,9,0,1,2,6,4,5};
int size = sizeof(arr)/sizeof(arr[0]);
SellSort(arr,size);
for (int i = 0;i < size;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void test3()//SelectSort
{
int arr[] = {6,5,1,7,2,9,1,4,6};
//int arr[] = {6,5,1,7,2,9,3,4,8};
int size = sizeof(arr)/sizeof(arr[0]);
//SelectSort(arr,size);
SelectSort_OP(arr,size);
for (int i = 0;i < size;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
void test4()//QuickSort QuickSort_NonR
{
int arr[] = {1,4,3,8,2,2,8,2,6};
//int arr[] = {4,1};
int size = sizeof(arr)/sizeof(arr[0]);
//QuickSort(arr,0,8);
//QuickSort(arr,0,1);
QuickSort_NonR(arr,0,8);
for (int i = 0;i < size;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
//test1();
//test2();
//test3();
test4();
system("pause");
return 0;
}</span></strong>
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정렬(2) - 삽입/힐/선택/빠른 정렬 및 최적화"Sort.h" test.cpp...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.