- it技术
- Sort
#include<iostream>
#include<vector>
#include<map>
using namespace std
;
void swap(vector
<int>& v
, int a
, int b
)
{
int temp
= v
[a
];
v
[a
] = v
[b
];
v
[b
] = temp
;
}
void Bubble_Sort(vector
<int>& v
)
{
int flag
= 0;
int len
= v
.size();
for (int i
= 0; i
< len
- 1; i
++)
{
flag
= 0;
for (int j
= 0; j
< len
- i
- 1; j
++)
{
if (v
[j
]>v
[j
+ 1])
{
swap(v
, j
, j
+ 1);
flag
= 1;
}
}
if (!flag
)
{
break;
}
}
return ;
}
void Violence_Sort(vector
<int>& v
)
{
int len
= v
.size();
for (int i
= 0; i
< len
- 1; i
++)
{
int min
= i
;
for (int j
= i
+ 1; j
< len
; j
++)
{
if (v
[j
] < v
[min
])
{
min
= j
;
}
}
if (min
!= i
)
{
swap(v
, i
, min
);
}
}
return ;
}
void Insert_Sort(vector
<int>& v
)
{
int len
= v
.size();
for (int i
= 1; i
< len
; i
++)
{
int key
= v
[i
];
int j
= i
- 1;
while (j
>= 0 && v
[j
] > key
)
{
v
[j
+ 1] = v
[j
];
j
--;
}
v
[j
+ 1] = key
;
}
return ;
}
void Shell_Sort(vector
<int>& v
)
{
int len
= v
.size();
int flag
= len
/ 2;
for (flag
; flag
> 0; flag
/= 2)
{
for (int i
= flag
; i
< len
; i
++)
{
int key
= v
[i
];
int j
= i
- flag
;
while (j
>= 0 && v
[j
] > key
)
{
v
[j
+ flag
] = v
[j
];
j
-= flag
;
}
v
[j
+ flag
] = key
;
}
}
return ;
}
int PartSort1(vector
<int>&v
, int left
, int right
)
{
int begin
= left
;
int end
= right
- 1;
int key
= v
[end
];
while (begin
< end
)
{
while (begin
< end
&&v
[begin
] <= key
)
{
begin
++;
}
while (begin
< end
&&v
[end
] >= key
)
{
end
--;
}
if (begin
< end
)
{
swap(v
, begin
, end
);
}
}
if (begin
!= right
- 1)
{
swap(v
, begin
, right
- 1);
}
return begin
;
}
int PartSort2(vector
<int>&v
, int left
, int right
)
{
int begin
= left
;
int end
= right
- 1;
int key
= v
[begin
];
while (begin
< end
)
{
while (begin
< end
&&v
[end
] >= key
)
{
end
--;
}
if (begin
< end
)
{
v
[begin
] = v
[end
];
begin
++;
}
while (begin
< end
&&v
[begin
] <= key
)
{
begin
++;
}
if (begin
< end
)
{
v
[end
] = v
[begin
];
end
--;
}
}
v
[begin
] = key
;
return begin
;
}
int PartSort3(vector
<int>&v
, int left
, int right
)
{
int cur
= 0;
int prev
= cur
- 1;
int key
=v
[right
-1];
while (cur
< right
)
{
if (v
[cur
] < key
&&++prev
!= cur
)
{
swap(v
, prev
, cur
);
}
cur
++;
}
swap(v
, ++prev
, right
- 1);
return prev
;
}
void Quick_Sort(vector
<int>& v
,int left
,int right
)
{
if (left
>= right
) return;
int div
= PartSort3(v
, left
, right
);
Quick_Sort(v
, left
, div
);
Quick_Sort(v
, div
+ 1, right
);
}
void MergeData(vector
<int>&v
, int left
, int mid
, int right
, vector
<int>&temp
)
{
int begin1
= left
, end1
= mid
;
int begin2
= mid
, end2
= right
;
int index
= left
;
while (begin1
< end1
&&begin2
< end2
)
{
if (v
[begin1
] <= v
[begin2
])
{
temp
[index
++] = v
[begin1
++];
}
else
temp
[index
++] = v
[begin2
++];
}
while (begin1
<end1
) temp
[index
++] = v
[begin1
++];
while (begin2
<end2
) temp
[index
++] = v
[begin2
++];
}
void _MergeSort(vector
<int>&v
, int left
, int right
, vector
<int>&temp
)
{
if (right
- left
> 1)
{
int mid
= left
+ ((right
- left
)>>1);
_MergeSort(v
, left
, mid
, temp
);
_MergeSort(v
, mid
, right
, temp
);
MergeData(v
, left
, mid
, right
, temp
);
for (int i
= 0; i
< (right
-left
); i
++)
{
v
[left
+ i
] = temp
[left
+ i
];
}
}
}
void MergeSort(vector
<int>& v
)
{
int len
= v
.size();
vector
<int>temp(len
);
_MergeSort(v
, 0, len
, temp
);
}
void AdjustDown(vector
<int>& v
,int len
,int parent
)
{
int child
= parent
* 2 + 1;
while (child
< len
)
{
if (child
+ 1 < len
&&v
[child
+ 1] < v
[child
])
{
child
++;
}
if (v
[child
] < v
[parent
])
{
swap(v
, child
, parent
);
parent
= child
;
child
= parent
* 2 + 1;
}
else
return;
}
}
void HeapSort(vector
<int>&v
)
{
int len
= v
.size();
for (int root
= (len
- 2) >> 1; root
>= 0; root
--)
{
AdjustDown(v
, len
,root
);
}
int end
= len
- 1;
while (end
)
{
swap(v
, 0, end
);
AdjustDown(v
,end
, 0);
end
--;
}
}
void my_swap(vector
<int>&v
, int num
)
{
int len
= v
.size();
int index
;
for (int i
= 0; i
< len
; i
++)
{
if (v
[i
] == 0) index
= i
;
}
swap(v
, index
, num
);
}
void Sort1(vector
<int>& v
)
{
int len
= v
.size();
int num
;
for (int i
= 0; i
< len
; i
++)
{
if (v
[i
] == i
) continue;
num
= i
;
my_swap(v
, i
);
for (int j
= 0; j
< len
; j
++)
{
if (v
[j
]==num
)
swap(v
,num
, j
);
}
}
}
void Printf(const vector
<int> v
)
{
for (auto ch
: v
)
{
cout
<< ch
<< " ";
}
cout
<< endl
;
}
void Test1()
{
vector
<int> v
{ 1, 4, 8, 5, 3, 9, 0, 2, 7, 6 };
Printf(v
);
}
int main()
{
Test1();
system("pause");
return 0;
}
